Java遞歸查找數組中的最大總和

我想弄清楚一個解決方案來計算數組中的最高總和。但是，我的限制是我不能在數組中使用相鄰的值。Java遞歸查找數組中的最大總和

如果我給出數組int [] blocks = new int[] {15, 3, 6, 17, 2, 1, 20};，計算的最高總和爲52（15 + 17 + 20）。我的目標是從遞歸解決方案轉到使用動態編程的解決方案，但是，我遇到了遞歸解決方案的問題。

，我已經初始化的基礎情況：

if(array.length == 0) 
    return 0; 
if(array.length == 1) 
    return array[0];

創建基本情況後，我不確定如何繼續遞歸過程。我最初試圖說，如果array具有一定的長度，那麼我可以計算出計算的最大值（Math.max）：例如，，例如。 if array.length = 3 return Math.max(array[0], array[1], array[2], array[0]+ array[2])

然後我遇到的問題是，我可以給一個長度爲100的數組。如何在此問題中使用遞歸？

來源

2017-04-23 Morgan Henry

爲什麼你要在你的例子'15 + 17 + 20'中只添加三個數字，輸出受限於三個數字？ – SomeDude

這些數字讓我得到最高的總和。我可以很容易地做到15 + 6 + 2 + 20，但那隻給我43. –

好吧，做15 + 3 + 6 + 17 + 2 + 1 + 20給我64.那會比你多12。 –

我認爲遞歸解決問題的方法是（在僞代碼）：

maxsum(A,0) = 0 
maxsum(A,1) = A[0] 
maxsum(A,k) = max(maxsum(A,k-2)+A[k-1], maxsum(A,k-1)), for k >= 2

凡maxsum(A,k)裝置，用於陣列A的子陣列從0開始和具有長度k最大總和。我相信你會很容易地將它翻譯成Java，它幾乎可以字面翻譯。

來源

2017-04-26 20:48:09 starikoff

Java遞歸查找數組中的最大總和

回答

相關問題