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

Constraints - `2 ≤ n ≤ 200000` - `1 ≤ L` - `1 ≤ M` - `L + M ≤ n` - `-10000 ≤ value ≤ 10000`