Maximum Value But Limited Neighbors

Question

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: (i) For each j, b[j] is 0 or 1, (ii) Array b has adjacent 1s at most k times, and (iii) sum_{j=1 to n} a[j]*b[j] is maximized. For example, given an array [100, 300, 400, 50] and integer k = 1, the array b can be: [0 1 1 0], which maximizes the sum to be 700. Or, 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.

Answer 1

Notation

MVBLN(i,m): Maximum value sum that can be achieved from the array A[1..i], using adjacent 1s at most m times.

Recurrence Relation

MVBLN(i,m) = max{MVBLN(i-1,m), MVBLN(i-1,m-1) + A[i], MVBLN(i-2,m) + A[i]}

Base Case: MVBLN(i,0) can be solved separately, using a separate problem, that we can call maximum value no neighbors.  MVNN(i) = max{MVNN(i-1), MVNN(i-2) + A[i]}. MVNN(0) = 0.  MVNN(1) = a[1].  MVNN(2) = max{a[1], a[2]}.

Optimality

MVBLN(i,m) is either an extension of MVBLN(i-1,m-1) that includes A[i], or extends MVBLN(i-2,m) that includes A[i], or something that uses MVBLN(i-1,m) and just ignores A[i].

Comments

Professor，why  there is only one 0 between 1s?

---

You can have two consecutive 0s also, no problem.  You won't have 3 consecutive 0s, as you can always take the middle 0 and change that 1 and get that extra value, for example if you have k = 1, and array as 100 1 0 100 0 0 100

---

What's the time complexity of this without using DP, just using recursion.