Algorithm to find maximum sum of elements in an ar

问题:

I came across this question. Given an array containing only positive values, you want to maximize the sum of chosen elements under the constraint that no group of more than k chosen elements are adjacent. For example if input is 1 2 3 1 7 9 (n=6 and k =2). The output will be 21, which comes from picking the elements _ 2 3 _ 7 9. My simple DP solution is this

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

But I am not sure whether this is the efficient solution. Can the complexity be further reduced? Thanks for your help

回答1:

Your code is correct (at least the thought is correct), also, Up to now, I have not found any wrong test data. Follow your thought, we can list the DP equation

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

In this equation, P(v) means the maximum in {C[v]~C[n]}(we let {C[1]~C[n]} be the whole list), so we just need to determine P(1).

I have not find a better solution up to now, but your code can be optimized, after you determine P(v), you can save the data i, so when you find P(v-1), you can just compare sum(C[v-1]+C[v]~C[v+i-1])+P[v+i+1] with P[v+1]+C[v] when i!=k, the worst complexity is the same, but the best complexity is linear.

回答2:

I think this will work :

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
}