Picks That Stay k Apart
Choose a non-empty set of indices so that any two chosen indices differ by at least
k, and print the largest possible sum of the chosen values. Values may be negative.
5 1 1 5, k = 2 -> 10 indices 0 and 3
2 7 9 3 1, k = 2 -> 12 indices 1 and 3, or 0 and 2 and 4
Problem #451 is this with k = 2, the no-two-adjacent problem. At k = 1 there is no
restriction at all, so the answer is the sum of every positive value. Seeing both of
those fall out of one recurrence is the point.
## The recurrence
Let best[i] be the largest sum of a non-empty selection whose LAST chosen index is
i. The previous chosen index, if there is one, can be anything at most i - k:
best[i] = a[i] + max( 0 taken as "nothing before", max over j <= i-k of best[j] )
written carefully so that the "nothing before" case does not become a licence to add zero to a negative running best.
The maximum over j <= i-k does not need a fresh scan. Keep one running value that
absorbs best[i-k] at step i and never shrinks:
runmax = -infinity
for i in 0..n-1:
if i-k >= 0: runmax = max(runmax, best[i-k])
best[i] = a[i] if runmax == -infinity else max(a[i], runmax + a[i])
answer = max(answer, best[i])
That makes it one pass. Rescanning the prefix for each i is O(n k) or O(n^2)
and is correct but slower.
## The two boundaries
runmax must start at negative infinity, not 0. Starting at 0 says "a selection with
nothing before it contributes 0", which is true, but it also lets a NEGATIVE running
best be replaced by 0, and that permits skipping a mandatory earlier pick. The
max(a[i], ...) branch is the correct way to express "start fresh at i".
The selection must be non-empty. -1 -2 -3 with k = 2 answers -1, the least bad
single pick, and a solution that allows the empty selection answers 0.
k may exceed n, in which case at most one index can be chosen and the answer is
the largest value.