數組中的Java遞歸差異

我目前正在學習Java，並且偶然發現我無法完成的練習。數組中的Java遞歸差異

任務是編寫一個遞歸方法，該方法接受一個數組並返回最大值和最小值的差值。

例如{12, 5, 3, 8}應返回5（8 - 3）。請注意，只允許按正確順序比較值（result = rightValue - leftValue）。例如12-3 = 9將不被允許。把它看作股票價值。你想知道哪個時間買賣股票賺取最大的利潤。

這很容易實現迭代，但我不知道如何做遞歸。也是通過分治來解決問題的一部分。

來源

2016-05-16 Nbert.

告訴我們你到目前爲止試過的東西 – attaboy182

@ Turing85不，只允許以正確的順序比較值。把它看作股票價值。你想知道哪個時間買賣股票賺取最大的利潤。 –

有太多可能的答案，或者對於這種格式，答案太長。請添加詳細信息以縮小答案集或隔離幾個段落中可以回答的問題。 +你的例子對我沒有意義。 –

我用鴻溝和征服這裏的做法。我相信這裏的訣竅是在我們將主數組分割的兩個數組中包含中間值。

/*這裏被忽略的邊緣情況*/

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); 

}

來源

2016-05-16 19:16:59 attaboy182

這解決了我的問題，非常感謝！ –

你能解釋爲什麼中間必須是「左+（左 - 右）/ 2」嗎？我預計它只是'（左 - 右）/ 2'。 –

-3

算法（這是相當多排序任務，則該減法步驟是微不足道的）

1）首先排序陣列（用於大陣列和較小的陣列遞歸插入遞歸歸併排序）。

合併排序（https://en.wikipedia.org/wiki/Merge_sort）

插入排序（https://en.wikipedia.org/wiki/Insertion_sort）

2）使用陣列最小索引[0]以獲得最小的值&指數[array.length-1]，以獲得最大

3）計算出的差異（不知道你用正確的順序是什麼意思？）

來源

2016-05-16 18:47:37 cyber101

這將導致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作爲較大的差異，並再次我不覺得這是因爲做到這一點的有效途徑。迭代對此會更好。

我希望這會有所幫助。

來源

2016-05-16 19:29:56

我知道遞歸對於這個練習來說是愚蠢的，但是它的一部分是迭代的，另一部分是遞歸的。謝謝你的幫助！ –

數組中的Java遞歸差異

回答

相關問題