Two Runs of Given Lengths
Choose two non-overlapping contiguous runs, one of length exactly L and one of length
exactly M, and print the largest possible total of the two runs. Either run may come
first. Values may be negative.
0 6 5 2 2 5 1 9 4, L = 1, M = 2 -> 20
The single element is the 9 at index 7, and the pair is 6 5 at indices 1 and 2,
for 9 + 11 = 20. Note that the greedy of taking the largest pair, 1 9 at indices
6 and 7, blocks the 9 and does worse.
Trying every pair of positions is O(n^2), and each sum is O(1) from prefix sums, so
the naive version is already reasonable at small n. The linear version is short enough
to be worth knowing.
## One order at a time
Because either run may come first, split into two cases and solve each with the same routine:
answer = max( best(L before M), best(M before L) )
Inside one case, sweep the position j of the SECOND run left to right, keeping the
best first run that ends before it:
bestFirst = -infinity
for j in 0 .. n-M:
if j-L >= 0: bestFirst = max(bestFirst, sum of the L-run starting at j-L)
if bestFirst is set: answer = max(answer, bestFirst + sum of the M-run at j)
The first run is absorbed at j - L, which is the last starting position whose run
ends at or before j. Absorbing at j instead lets the two runs overlap and the answer
comes out too large, which is the mistake this problem is built around.
## Two details
Run sums come from prefix sums, so each is O(1). Values may be negative, so the
answer may be negative and bestFirst must not start at 0. -1 -2 -3 with
L = M = 1 answers -3, the two least bad singles, and a solution starting at 0
answers -1.
L + M never exceeds n, so a valid pair always exists and there is no impossible
case to report.
Both orders must be tried. 4 -1 4 -1 4 with L = 2, M = 1 answers 7, and only one of
the two orders reaches it.