464. The Best Alternating Sum

Choose a non-empty SUBSEQUENCE and score it by adding the first element, subtracting the second, adding the third, and so on. Print the largest score any subsequence can reach.

4 2 5 3 -> 7 choose 4 2 5: 4 - 2 + 5 = 7 5 6 7 8 -> 8 choose 8 alone

Whether the next chosen element is added or subtracted depends only on how many have been chosen so far, and only on its PARITY. So the state is one bit:

odd best score with an odd number chosen, so the last one was ADDED even best score with an even number chosen, so the last one was SUBTRACTED

and each element either extends one of them or is skipped:

odd = max(odd, even + a[i]) even = max(even, odd - a[i])

The initial values carry the meaning. even = 0 represents choosing nothing at all, which is a legal prefix of a construction even though the final subsequence must be non-empty. odd starts at negative infinity, because before any element is seen no odd-length choice exists.

The answer is odd, never even. Any even-length subsequence ends on a subtraction, so deleting that last element gives an odd-length one with a LARGER score. An even-length choice is therefore never optimal, and reading max(odd, even) is the same as allowing the empty subsequence, which would answer 0 on an all-small input.

Trace 1 1 1: the answer is 1, since taking two elements scores 0 and taking three scores 1 again. A solution that reports 0 has read even.

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