At most k adjacent 1s (Maximum Value limited neighbors)

Question

In my algorithms course, there's a question in the book that goes as follows: "You are given an array a[1..n] of positive numbers and an integer k. You have to produce an array b[1..n], such that: for each j, b[j] is either 1 or 0. Array b has adjacent 1s at most K times. Sum(a[j]*b[j]) for 1 <= j <= n is maximized." For example given an array [10, 100, 300, 400, 50, 4500, 200, 30, 90] and k = 2 the array b can be = [1, 0, 1, 1, 0, 1, 1, 0, 1] which maximizes the sum to 5500.

The solution uses Dynamic programing when discussing this with some friends they said the recurrence relation is of the form M(i, j) = max(M(i-2, j) + a[i], M(i-1, j-1) + a[i])

can someone explain why so? or if they have a different form of solving such a problem. I find Dynamic programing a bit hard to grasp. Thank you.

Answer 1

M[i, j] is max sum from 1 to i, with j adjacent 1s

M[i,j] can be computed as the max of 3 situations:

b[i]=0  =>  S=M[i-1, j]   // a[i] not added to sum, b[1..i-1] has same number of adjacent 1s (j) as b[1..i] because b[i] is zero

b[i]=1 and b[i-1]=0  => S=M[i-2, j]+a[i]   // a[i] added to sum, b[1..i-2] has same number of adjacencent 1s, because b[i-1] is zero

b[i]=1 and b[i-1]=1  => S=M[i-1, j-1]+a[i]   // a[i] added to sum, since b[i] and b[i-1] are both 1, they count as adjacent 1s, so b[1..i-1] contains only j-1 adjacent 1s

The recursive rule is the max of the 3 sums above. The end condition is M[1, j]=a[1] because b[1..1] has only one item b[1]=1 and no adjacent 1s.

The answer we need is M[n, k].

Complexity is O(nk).