701. Taking k From the Two Ends
Take exactly k values, each time from the FRONT or the BACK of the array. Print the largest
total you can take.
1 2 3 4 5 6 1, k = 3 -> 12 take 1 from the front and 6, 5 from the back
1 79 80 1 1 1 200 1, k = 3 -> 202
2 2 2, k = 2 -> 4
## What is left behind
Taking a prefix and a suffix of total length k leaves a contiguous MIDDLE of length
n - k. Maximising what is taken is minimising what is left:
answer = (whole sum) - (smallest total of a window of length n - k)
The original wording has two moving ends and no obvious window. Rewriting it as "what remains" produces a window of FIXED length, which one slide handles. That rewriting is the whole problem, and it is the same inversion problem 694 uses.
## The sweep
m = n - k
cur = sum of a[0 .. m-1]
mn = cur
for i in m .. n-1:
cur += a[i] - a[i - m]
mn = min(mn, cur)
answer = total - mn
## The case the loop cannot express
k = n, meaning everything is taken. Then m = 0, the middle is empty, and the answer is the
whole sum. A window of length 0 is not something the slide can build, so this is handled before
it.
That is the same empty-middle boundary as problem 694, and it is missed for the same reason.
## Why searching over the split is wasteful
Trying every "take p from the front and k - p from the back" with fresh sums is O(k^2);
with prefix sums it is O(k) and correct too. The window version is O(n) and needs no
second array, but the important part is that all three rest on the same observation about what
is left behind.
## Overflow
200000 values of up to 10^4 total exactly 2 * 10^9. The move here is to check that
figure against the limit rather than to recognise the shape: a signed 32 bit integer holds
up to 2147483647, so 2000000000 FITS, with about seven percent to spare. This problem
has no overflow, and a 64 bit accumulator buys margin rather than correctness.
The margin is thin enough to be worth the arithmetic. Raise the value cap to 10^5 and the
total becomes 2 * 10^10; raise the length cap to 10^6 and it becomes 10^10. Either
one is an order of magnitude past what 32 bits holds.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `1 ≤ each value ≤ 10^4`
Input
The first line contains two integers n and k.
The second line contains n positive integers.
Output
Print one integer, the largest total that can be taken.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.