k個以下の要素が隣接しないような要素配列の最大和を求めるアルゴリズム

Question

---

こんにちは、 私はこの質問に出会いました。正の値のみを含む配列が与えられます。要素を追加することによって最大合計を見つける必要があります。条件は、隣接するk個以上の要素を選択できないことです。私の簡単な解決策は、すべてのケースで正しい入力を生成しません。この

---

​​

---

この解決策です。なぜ私は理解できません。 誰でも助けてくれますか？ありがとうございました。

Answer 1

コードでは、k+1番目の要素をスキップするだけです。場合によっては、より多くの要素をスキップするのが良いですが、それを賢明に行うのが良いでしょう。 （など、上のスキップする最低の数字を選択してください）

編集：いくつかの簡単な再帰的な解決策：（それは効果的ではないが、動作します）

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