The Best Run of Exactly k
Given n integers and a length k, print the largest sum of any k CONSECUTIVE values.
Values may be negative.
1 2 3 4 5, k = 2 -> 9
-1 -2 -3, k = 2 -> -3
## Why there is nothing to memoise
Dynamic programming pays for itself when subproblems REPEAT. That is the "overlapping subproblems" half of the usual definition, and it is the half that fails here.
There are n - k + 1 windows. Each one is needed once and never consulted again, so there is
nothing to look up and a table is pure overhead: it stores n values to answer n questions,
each asked once.
A correct instinct, misapplied. Checking that subproblems actually recur, before reaching for a table, is a cheap habit and this problem is the reminder.
## Slide, do not re-add
Computing each window from scratch is O(n * k), which at n = 200000 and k = 100000 is
2 * 10^10 additions.
Consecutive windows overlap in k - 1 values, so one subtraction and one addition move from
each window to the next:
s = a[0] + ... + a[k-1]
best = s
for i from k to n-1:
s = s - a[i-k] + a[i]
best = max(best, s)
This is worth separating from memoisation in your head. Memoisation stores answers to reuse them; a sliding window stores nothing and instead UPDATES a value incrementally. Both avoid repeated work, by different means.
## Negative values and the starting best
Start best at the first window's sum, never at 0. All values may be negative, and 0 is not an
available answer: -1 -2 -3 with k = 2 answers -3.
Seeding a running maximum at zero is the recurring bug across this whole subject, and it is in the tests here too.
## Boundaries
k = n gives one window, the whole array. k = 1 gives the largest single value.
## Overflow
200000 values of magnitude 10^9 reach 2 * 10^14, so use 64 bits. That is still exact in a
double, so JavaScript is fine with ordinary numbers.
## Cost
Time O(n). Space O(1) beyond the input.