The Best Alternating Sum of a Run
Score a CONTIGUOUS non-empty run by adding its first element, subtracting its second, adding its third, and so on. Print the largest score any run can reach.
4 2 5 3 -> 7 the run 4 2 5: 4 - 2 + 5
2 -3 4 -> 9 the whole run: 2 + 3 + 4
The second line is the case that makes this problem worth having. A negative element in a subtracting position becomes a gain, so a run can be worth more than the sum of its absolute values suggests.
Problem #464 is this for SUBSEQUENCES. There the state was a single parity bit and every element could be skipped. Here nothing may be skipped, so the state has to say something different.
## What the state is
plus[i] best score of a run ending at i where a[i] is ADDED
minus[i] best score of a run ending at i where a[i] is SUBTRACTED
plus = max( a[i], minus_before + a[i] )
minus = plus_before - a[i]
The asymmetry is the point. plus may START a fresh run at i, because a run's first
element is always added. minus may NOT: a run cannot begin with a subtraction, so
minus has no a[i] alone branch and is undefined until plus_before exists.
That is the difference from #464, where every state could be reached by skipping, and it is why the same two-line recurrence shape means something else here.
## Reading the answer, where this parts company with #464
In #464 the values are positive, and there the answer is the ADDED state only: a subsequence ending on a subtraction always improves by dropping that last element, because the dropped value was positive.
Here values may be negative, and that argument collapses. Subtracting a negative ADDS. So a run ending on a subtraction can be the best run, and the answer is
max over i of max( plus[i], minus[i] )
-3 -1 -2 is the case. The best run is -1 -2, scoring -1 - (-2) = 1, and it ends
on a subtraction. Taking only plus reports -1 here, which is the largest single
element and looks entirely reasonable.
Carrying the #464 argument across unchanged is the trap, and it is worth noticing that the argument did not break because the recurrence changed. It broke because the CONSTRAINTS changed.
## Boundaries
So -3 -1 -2 answers 1: not -1 from reading plus alone, and not 0, which is what
allowing an empty run gives. Both are plausible-looking wrong answers, which is why this
input is a test.
1 1 1 answers 1 and 7 0 7 answers 14, the whole run, since subtracting 0 costs
nothing.