Take the 2-minute tour ×

Almost the same as this: find maximum sum of elements in an array such that not more than k elements are adjacent

except there is a limit of n elements we can choose. How to modify the DP algorithm to make it work for this?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

well, let me make it more clearly.

question: find maximum sum of n elements in an array such that not more than K elements are adjacent

let int f[i][j][k] means the maximum sum for first i elements, using j total elements and the last k elements are used. let bool g[i][j][k] denotes whether it is possible to get certain combination. eg. g[1][1][2] is false. this is important because without restrict, f may generate impossible answers.

initially, memset f and g to be all zeros and set g[0][0][0] to be true. we can use forward recurrence to solve this DP problem. obviously, each time you encounter a number, you have two choices: choose it, or abadon it. thay gives out the recurrence formula:

f[i][j][k] can infer f[i+1][j+1][k+1], or
f[i][j][k] can infer f[i+1][j][0]

so, the pseudo code can be as follow:

        for (int k=0;k<=K;k++) if (g[i][j][k]) {

and the final result will be:

for (i=0;i<=K;i++)
return ans;

above gives exactly j elements. if you want to get at most j elements, you can change it in this way:

    for (j=0;j<=K;j++)
return ans;
share|improve this answer
@WilliamRookwood first of all, i think i made a small mistake in my original code. i will edit my post shortly. –  songlj Feb 10 '13 at 8:29
@WilliamRookwood Did I answer your question? Do you need more help? –  songlj Feb 12 '13 at 5:32
yes it did, thank you! –  William Rookwood Feb 12 '13 at 6:18

Add new dimension of DP function: f[i, j, l] - max sum for first i elements, if used j total elements and last l elements in this sum.

share|improve this answer
Hi, I'm having trouble figuring out the recurrence formulas, could you show the recurrence formula? Thanks –  William Rookwood Feb 7 '13 at 7:51
For example, P(v,i) = P(v-1,i-1) + C(v) if i > 0 , P(v,0) = max(P(v-1,i) for i = 0..min(k, v)) , P(0,0) = 0 were the recurrence formulas in the other post I linked to. Can you provide the formulas for the f[i, j, l] function? –  William Rookwood Feb 7 '13 at 8:25

Your Answer


