我目前正在學習Java,並且偶然發現我無法完成的練習。數組中的Java遞歸差異
任務是編寫一個遞歸方法,該方法接受一個數組並返回最大值和最小值的差值。
例如{12, 5, 3, 8}
應返回5
(8 - 3
)。請注意,只允許按正確順序比較值(result = rightValue - leftValue
)。例如12-3 = 9
將不被允許。把它看作股票價值。你想知道哪個時間買賣股票賺取最大的利潤。
這很容易實現迭代,但我不知道如何做遞歸。也是通過分治來解決問題的一部分。
我目前正在學習Java,並且偶然發現我無法完成的練習。數組中的Java遞歸差異
任務是編寫一個遞歸方法,該方法接受一個數組並返回最大值和最小值的差值。
例如{12, 5, 3, 8}
應返回5
(8 - 3
)。請注意,只允許按正確順序比較值(result = rightValue - leftValue
)。例如12-3 = 9
將不被允許。把它看作股票價值。你想知道哪個時間買賣股票賺取最大的利潤。
這很容易實現迭代,但我不知道如何做遞歸。也是通過分治來解決問題的一部分。
我用鴻溝和征服這裏的做法。我相信這裏的訣竅是在我們將主數組分割的兩個數組中包含中間值。
/*這裏被忽略的邊緣情況*/
int findMax(int[] arr, int left, int right){
if(right-left == 1) return (arr[right]-arr[left]);
int middle = left + (right-left)/2;
int max1 = findMax(arr, left, middle);
int max2 = findMax(arr, middle, right);
if(max1 >= 0 && max2 >= 0) return max1+max2;
else return Math.max(max1,max2);
}
這解決了我的問題,非常感謝! –
你能解釋爲什麼中間必須是「左+(左 - 右)/ 2」嗎?我預計它只是'(左 - 右)/ 2'。 –
算法(這是相當多排序任務,則該減法步驟是微不足道的)
1)首先排序陣列(用於大陣列和較小的陣列遞歸插入遞歸歸併排序)。
合併排序(https://en.wikipedia.org/wiki/Merge_sort)
插入排序(https://en.wikipedia.org/wiki/Insertion_sort)
2)使用陣列最小索引[0]以獲得最小的值&指數[array.length-1],以獲得最大
3)計算出的差異(不知道你用正確的順序是什麼意思?)
這將導致12-3 = 9,OP明確表示不是答案。 – mks
如果您對數組進行排序,那麼您不必擔心訂單。我被具體要求實施分而治之算法。 –
我不得不承認,我沒有很好地解釋我的問題是什麼。此任務旨在模擬股票市場。您試圖通過以最低價格購買並以最高價格出售來最大化您的利潤。 –
嗯,我不認爲遞歸是在這個非常有效的。你可能永遠不會這樣做(除了家庭作業)。像這樣的東西會做:
int findGreatestDifference(Vector<Integer> numbers, int greaterDifference){
if(numbers.size() == 1) //return at last element
return greaterDifference;
int newDifference = (numbers.get(0) - numbers.get(1));
if (newDifference > greaterDifference)
greaterDifference = newDifference;
numbers.remove(numbers.size() - 1);
findGreatestDifference(numbers, greaterDifference);
return greaterDifference;
}
第一次調用它,傳遞0作爲較大的差異,並再次我不覺得這是因爲做到這一點的有效途徑。迭代對此會更好。
我希望這會有所幫助。
我知道遞歸對於這個練習來說是愚蠢的,但是它的一部分是迭代的,另一部分是遞歸的。謝謝你的幫助! –
告訴我們你到目前爲止試過的東西 – attaboy182
@ Turing85不,只允許以正確的順序比較值。把它看作股票價值。你想知道哪個時間買賣股票賺取最大的利潤。 –
有太多可能的答案,或者對於這種格式,答案太長。請添加詳細信息以縮小答案集或隔離幾個段落中可以回答的問題。 +你的例子對我沒有意義。 –