On a game show, numbered tokens lie in a row with values vals. The contestant walks from left to right once and may pocket any tokens they pass. The score is computed in pocketing order with alternating signs: the 1st pocketed token is added, the 2nd subtracted, the 3rd added, and so on. Pocketing nothing scores 0. Return the best possible score.
Examples
Input: vals = [6, 2, 1, 5, 4, 8]
Output: 14
Explanation: pocket 6, 1, 5, 4, 8: 6 - 1 + 5 - 4 + 8 = 14.
Input: vals = [-3, -1]
Output: 0
Constraints
0 <= len(vals) <= 10**5-10**4 <= vals[i] <= 10**4- Target complexity: O(n) time; the number of possible pick sets is 2^n.
Goals
- Keep the best score for an odd and an even number of picks
- Allow skipping any element, including all of them