Watch 10 video solutions for Maximum Alternating Subsequence Sum, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCode has 31,710 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.
[4,2,5,3] is (4 + 5) - (2 + 3) = 4.Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.
Example 1:
Input: nums = [4,2,5,3] Output: 7 Explanation: It is optimal to choose the subsequence [4,2,5] with alternating sum (4 + 5) - 2 = 7.
Example 2:
Input: nums = [5,6,7,8] Output: 8 Explanation: It is optimal to choose the subsequence [8] with alternating sum 8.
Example 3:
Input: nums = [6,2,1,2,4,5] Output: 10 Explanation: It is optimal to choose the subsequence [6,1,5] with alternating sum (6 + 5) - 1 = 10.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: You are given an integer array and must choose a subsequence whose alternating sum is maximized. The alternating sum means elements are added and subtracted in order: a0 - a1 + a2 - a3 .... The subsequence can skip any elements but must keep the original order. The challenge is deciding which numbers to include so the positive positions carry large values while negative positions carry smaller ones.
Approach 1: Dynamic Programming (O(n) time, O(1) space)
This problem maps naturally to dynamic programming. While scanning the array, track two states: the best alternating sum when the next operation is addition (even index in the subsequence) and the best sum when the next operation is subtraction (odd). For each number x, you either include it or skip it. Including it transitions between states: adding x updates the even state, subtracting x updates the odd state.
The recurrence is straightforward: update the "add" state using the previous subtract state plus the current value, and update the "subtract" state using the previous add state minus the value. Because only the previous states matter, you store just two variables instead of a full DP table. This reduces space complexity to O(1) while keeping time complexity O(n).
Approach 2: Greedy with Two Accumulators (O(n) time, O(1) space)
A greedy interpretation leads to an even simpler implementation. Maintain two accumulators: add for the best sum when the next operation is addition and subtract for the best sum when the next operation is subtraction. Iterate through the array once. For each value, compute the best new states by either taking the element or skipping it.
The key insight: if a value improves the alternating pattern, include it immediately. Updating the accumulators effectively captures the same transitions as the DP solution but framed as a greedy decision process. Since each element is processed exactly once and only constant variables are used, the algorithm runs in O(n) time with O(1) space.
This approach is often easier to reason about because the two accumulators represent the best possible sums for even and odd positions in the subsequence. The logic mirrors classic stock-trading style DP problems where you alternate between "buy" and "sell" states.
Recommended for interviews: The greedy two-accumulator version is what most interviewers expect. It demonstrates strong understanding of state transitions and optimization from dynamic programming to constant-space logic. Explaining the DP formulation first shows you understand the state definition, while deriving the greedy version highlights optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (State Transition) | O(n) | O(1) | Best for understanding the problem formally using DP states for add and subtract positions |
| Greedy with Two Accumulators | O(n) | O(1) | Preferred interview solution; simple implementation with constant memory |