如何找到一個數組中的非相鄰數字的最大總和的數字指數

Question

我已經想出了算法來找到數組中的非相鄰元素的最大總和，但我有一些麻煩找到哪些數字是摘取總結。這裏是我的最大總和（不包括一些初始化）算法：

int n; //number of cells. Cells are labeled from 1 to n 
int num[]; // all the numbers 
int findMax[]; // findMax[i] equals to the current maximum score 
for (int i = 0; i<n; i++){ 
    if (i == 0){ 
     findMax[0] = num[0]; 
    } 
    else if (i == 1){ 
     findMax[1]= Math.max(findMax[0],num[1]); 

    } 
    else{ 
     findMax[i]=Math.max(findMax[i-2]+num[i], findMax[i-1]); 

} 
return findMax[n]; 

它不是那麼明顯，我讓我們選取號碼的指數之。有人可以給我任何有關這方面的見解嗎？謝謝！

Answer 1

使用自己的條件來獲得最佳變體而不是Math.max。

當您從兩個變體中選擇最大值時，請將最佳變體索引寫入一些額外的存儲（數組）中。

最後展開最佳組合的曲目。

我希望這個線索足以解決任務。