查找元素數組的最大總和的算法，使得不超過k個元素相鄰

Question

---

嗨， 我碰到過這個問題。給定一個只包含正值的數組。您需要找到添加元素可能導致的最大總和。條件是你不能選擇超過k個相鄰的元素。我簡單的解決辦法是這樣的

---

​​

---

該解決方案在所有情況下都不會產生正確的輸入。我無法弄清楚爲什麼。 任何人都可以幫忙嗎？謝謝。

Answer 1

在您的代碼中，您只需跳過每個k+1 th元素。有時候，最好跳過更多的元素，但要明智地去做。 （選擇最低的數字來跳過，等）

編輯：一些簡單的遞歸解決方案：（這不是有效的，但將工作）

long maxsum(int n,int k,long *profits) { 
    long sum=0,max=0,cur; 
    int i; 
    if (n<=k) { 
     for (i=0;i<n;i++) sum+=profits[i]; 
     return sum; 
    } 
    for (i=0;i<=k;i++) { 
     cur=sum+maxsum(n-i-1,k,profits+i+1); 
     if (cur>max) max=cur; 
     sum+=profits[i]; 
    } 
    return max; 
}