Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 6 down vote favorite

I came across this question. Given an array containing only positive values, you want to maximize the sum of choosen elements under the constraint that no group of more than k choosen 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

share|improve this question
2  
"cannot pick more than k adjacent elements" is confusing. Do you mean "cannot pick more than k elements, and they must be adjacent" or do you mean "can pick as many as you like, as long as no group of more than k are adjacent"? – Keith Randall Apr 6 '12 at 16:16
3  
Please work on you acceptance rate. Go back and accept some of the answers for your questions. – Yochai Timmer Apr 6 '12 at 16:18
I updated the question, it's clear from the example he meant the latter. – rrenaud Apr 6 '12 at 17:05
Is this homework? If so, it should be tagged as such. – Perry Apr 6 '12 at 17:50
No, its not homework – Gopikanna Apr 6 '12 at 17:52
show 3 more comments

2 Answers

up vote 1 down vote

If you can only choose adjacent items, and they are all positive, then you can do it in one loop.

Just open a window of K elements (loop through the first K elements), put that value as the local maximum, and for the rest of the array, just add the next item and substract the last item each time you move. This way you can see all the windows of K elements in one loop.

share|improve this answer
I am not following it, for example if input is 1 2 3 1 7 9 n=6 and k =2. The output will be 21. which will be the sum by picking following elements _ 2 3 _ 7 9 – Gopikanna Apr 6 '12 at 16:54
up vote 0 down vote

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
}
share|improve this answer
Sorry..I am not able to figure out your algorithm..Any way its recursive.. It looks to have more complexity than mine.. – Gopikanna Apr 7 '12 at 1:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.