查找元素数组的最大总和的算法，使得不超过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; 
}