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

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ value ≤ 1000000000`