472. 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.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 200000` - `-1000000000 ≤ value ≤ 1000000000`