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.