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

Question

私はこの問題に遭遇しました。正の値のみを含む配列が与えられた場合、選択したk個以上の要素のグループが隣接していないという制約の下で、選択された要素の合計を最大にしたいとします。たとえば、入力が1 2 3 1 7 9（n = 6、k = 2）の場合出力は、要素を選んでから来ている21、_ 2 3 _ 7 9.私の簡単なDPソリューションは、この

#include<stdio.h> 
#include<limits.h> 
#include<malloc.h> 


long maxsum(int n,int k,long *sums){ 
    long *maxsums; 
    maxsums = malloc(sizeof(long)*n); 
    int i; 
    long add = 0; 
    for(i=n-1;i>=n-k;i--){ 
     add += sums[i]; 
     maxsums[i] = add; 
    } 

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

int main(){ 
    int cases=0,casedone=0; 
    int n,k; 
    long *array; 
    long maxsum = 0; 
    fscanf(stdin,"%d %d",&n,&k); 
    array = malloc(sizeof(long)*n); 
    int i =0; 
     while(casedone < n){ 
      fscanf(stdin,"%ld",&array[casedone]); 
     casedone++; 
     } 
    printf("%ld",maxsum(n,k,array)); 
} 

あることでしょう。しかし、私は、これは効率的なソリューションであるかどうかを確認していません。複雑さをさらに減らすことはできますか？おかげであなたの助け

Answer 1

のために、私はこれがうまくいくと思う：

findMaxSum(int a[], int in, int last, int k) { // in is current index, last is index of last chosen element 
    if (in == size of a[]) return 0; 
    dontChoseCurrent = findMaxSum(a, in+1, last, k); // If current element is negative, this will give better result 
    if (last == in-1 and k > 0) { // last and in are adjacent, to chose this k must be greater than 0 
     choseCurrentAdjacent = findMaxSum(a, in+1, in, k-1) + a[in]; 
    } 
    if (last != in-1) { // last and in are not adjacent, you can chose this. 
     choseCurrentNotAdjacent = findMaxSum(a, in+1, in, k) + a[in]; 
    } 
    return max of dontChoseCurrent, choseCurrentAdjacent, choseCurrentNotAdjacent 
} 

Answer 2

あなたのコードが正しいか（少なくとも、考えが正しい）、また、今までは、私が間違ったテストデータを発見していません。あなたの考えに従ってください、私たちはDP方程式

この式で

P(v)=max{sum(C[v]~C[v+i-1])+P(v+i+1),0<=i<=k}

を一覧表示することができ、P（v）はで最大値を意味し、{C [V]〜C [n]は}（私たちは聞かせて、{C [1] 〜C [n]}は全体のリストです）、P（1）を決定するだけです。

P（v）を決定した後、データiを保存することができるので、コードを最適化することができます.P（v-1）を見つけると、次のことができます。 i！= 1のときP [v + 1] + C [v]と総和（C [v-1] + C [v] ~C [v + i-1]）+ P [v + k、最悪の複雑さは同じですが、最良の複雑さは線形です。