651. Maximum Alternating Subsequence Sum
You are given an array nums of positive integers.
Pick any non-empty subsequence (keep the original order, drop whichever elements you like) and score it alternately: add the elements at even positions of the picked sequence (positions 0, 2, 4, … after re-indexing) and subtract the elements at odd positions (1, 3, 5, …).
For instance, picking [4, 2, 5] scores 4 − 2 + 5 = 7.
Return the maximum score any subsequence can achieve. Note the answer can exceed 32-bit range on large inputs.
Example 1:
Input: nums = [4, 2, 5, 3]
Output: 7
Explanation: Pick the subsequence [4, 2, 5]: it scores 4 − 2 + 5 = 7. No other pick beats it — e.g. [5] scores 5 and [4, 2, 5, 3] scores 4 − 2 + 5 − 3 = 4.
Example 2:
Input: nums = [6, 2, 1, 2, 4, 5]
Output: 10
Explanation: Pick [6, 1, 5]: 6 − 1 + 5 = 10. Subtracting the small dip at 1 lets both peaks 6 and 5 count positively.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁵
Hints:
Trying every subsequence is O(2^n). For each element there are only two things that matter: do you take it, and does it land on an even or odd position of your picked sequence?
Define two running bests: the highest score of a subsequence whose last pick sat at an even position, and the highest whose last pick sat at an odd position. How does one new element update both?
even' = max(even, odd + x) and odd' = max(odd, even − x), updated simultaneously. Start even = odd = 0 and answer with even — since values are positive, the best sequence always ends on an added element.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 2, 5, 3]
Expected output: 7