459. The Best Run With One Removal
Print the largest sum of a non-empty contiguous run, where you may optionally DELETE one element from inside the run. After the deletion the run must still be non-empty.
1 -2 0 3 -> 4 take 1 -2 0 3 and delete the -2
1 -2 -2 3 -> 3 deleting one -2 is not enough, so just take 3
The obstacle is that a decision made earlier, whether the deletion has been used, changes what is allowed later. So one running value cannot express it.
Carry two:
keep best run ending here with NO deletion used
drop best run ending here with the deletion already used
and each extends the other:
keep = max(a[i], keep + a[i]) the ordinary scan
drop = max(keep_before, drop + a[i]) delete a[i] now, or delete earlier and keep a[i]
The first branch of drop is the interesting one: keep from the PREVIOUS index
means the run continues but skips a[i] entirely, which is exactly what deleting it
means.
Both must read the previous values before either is overwritten.
The all-negative case is the check that matters. -1 -1 -1 -1 answers -1: the run
must stay non-empty after the deletion, so the best is a single element, and a
solution that starts drop at 0 reports 0 instead.
Constraints - `1 ≤ n ≤ 200000` - `-10000 ≤ value ≤ 10000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print the largest sum of a non-empty run, optionally deleting one element from it.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.