Picking k From Either End
Take exactly k elements, one at a time, each from the FRONT or the BACK of what
remains. Print the largest possible total. Values may be negative.
1 79 80 1 1 1 200 1, k = 3 -> 202 take 1 from the front? no
The answer 202 comes from taking from the BACK three times: 1 + 200 + 1. Taking the
front first gives at most 1 + 79 + 80 = 160.
Problem #426 looks like this one and is a different problem. There, two players alternate and each takes an end, so every move changes what the OPPONENT can reach and the answer needs a minimax over the remaining range. Here there is one player, the count is fixed, and nobody responds. That difference is what collapses the search below.
## The observation that removes the search
There are 2^k orders, and a table over "front index, back index" is O(k^2) states.
Neither is needed, because the ORDER of the picks does not affect the total.
Whatever sequence of front and back picks you make, the result is some number of elements from the front and the rest from the back. Only the SPLIT matters. So enumerate the split directly:
answer = max over i in 0..k of ( sum of the first i ) + ( sum of the last k-i )
With prefix sums that is O(k) total, and the whole search collapses to one loop. The
step from 2^k to O(k) came from noticing that a decision sequence is really just a
count.
## Two boundaries
i = 0 and i = k are both legal, so the loop runs over k + 1 values. Taking all
from one end must be reachable, and that is what 1 1000 1 with k = 1 tests: the
answer is 1, not 1000, because only the two ends are ever available.
k = n means taking everything, so the answer is the whole sum no matter what.
1 2 3 4 5 with k = 5 answers 15, and a loop ending at k - 1 gets it wrong.
Values may be negative, so the answer may be negative. -1 -2 -3 with k = 1 answers
-1. Taking is mandatory, so there is no option to take nothing.
Totals reach 2 * 10^5 times 10^9, so accumulate in 64 bits.