Maximum Alternating Subsequence Sum: Two-State DP
You are given a 0-indexed array nums. The alternating sum of a subsequence is computed by adding the elements at even positions in the subsequence and subtracting the elements at odd positions. Your task is to find the maximum alternating sum over all possible subsequences of the array.
This is LeetCode 1911: Maximum Alternating Subsequence Sum, and it is one of the cleanest examples of two-state dynamic programming. If you have solved any of the "Best Time to Buy and Sell Stock" problems, the pattern here will feel familiar.
Why this problem matters
This problem teaches you a powerful technique: tracking two alternating states as you iterate through an array. Instead of building a full DP table or trying all subsequences, you maintain just two variables and update them at each step.
The same two-state pattern appears in:
- Best Time to Buy and Sell Stock II (unlimited transactions)
- House Robber (take or skip decisions)
- Best Time to Buy and Sell Stock with Cooldown (state machine DP)
Master the two-state approach here, and you will recognize it immediately in those problems.
The key insight: it is like stock trading
The trick is to realize that picking elements for an alternating subsequence is equivalent to a series of "buy" and "sell" decisions.
Think of it this way. You walk through the array and maintain two states:
- even: you are looking to pick an element at an even position in your subsequence (it gets added). This is like "buying" a stock.
- odd: you have already picked an even-position element and are now looking to pick an odd-position element (it gets subtracted). This is like "selling" a stock.
When you are in the "even" state and you encounter a large number, you want to pick it (add it to your sum). When you are in the "odd" state and you encounter a small number, you want to pick it (subtracting a small number hurts less). The answer is just the maximum value of the "even" state after processing all elements, because the optimal subsequence always ends with a positive contribution.
If you have solved Best Time to Buy and Sell Stock II, you have already solved this problem. The "even" state corresponds to "holding no stock" (looking to buy), and the "odd" state corresponds to "holding stock" (looking to sell). The mechanics are identical.
The approach: two-state DP
At each element, maintain two values:
even: best alternating sum when the next pick would be at an even position (added)odd: best alternating sum when the next pick would be at an odd position (subtracted)
Transitions:
even = max(even, odd + nums[i])-- either skip or pick this element at an even positionodd = max(odd, even - nums[i])-- either skip or pick this element at an odd position
def max_alternating_sum(nums):
even, odd = 0, 0
for num in nums:
even, odd = max(even, odd + num), max(odd, even - num)
return even
That is the entire solution. Five lines. Let's walk through why each transition works.
When you compute max(even, odd + num), you are asking: "Is it better to keep my current even-state sum, or should I pick this element after being in the odd state?" Picking it means you add it (even-position contribution) on top of whatever alternating sum you had when you were last in the odd state.
When you compute max(odd, even - num), you are asking: "Is it better to keep my current odd-state sum, or should I pick this element after being in the even state?" Picking it means you subtract it (odd-position contribution) from your best even-state sum.
Initialize: even = 0, odd = 0
Before processing any element, both states are 0. "even" means the next pick will be added. "odd" means the next pick will be subtracted.
Step 1: Process nums[0] = 4
Pick 4 at an even position (add it) to get even = 4. Subtracting 4 from 0 would be negative, so odd stays at 0.
Step 2: Process nums[1] = 2
Adding 2 to odd (0+2=2) does not beat the current even of 4, so even stays. But 4-2=2 is better than old odd of 0, so odd updates to 2.
Step 3: Process nums[2] = 5
Picking 5 after an odd state gives 2 + 5 = 7, which beats the old even of 4. This corresponds to subsequence [4, 2, 5] with sum +4 - 2 + 5 = 7.
Step 4: Process nums[3] = 3
Adding 3 to odd (2+3=5) does not beat even = 7, so even stays. Subtracting 3 from 7 gives 4, better than old odd of 2. Final answer: even = 7.
Why the answer is always even
The optimal subsequence always ends on an element at an even position (a positive contribution). Why? If the last element in your subsequence is at an odd position, you are subtracting it. Removing that last element from the subsequence would only increase your sum. So there is never a reason for the optimal subsequence to end at an odd position.
This means the answer is always the even state after processing all elements.
A common mistake is to return max(even, odd) at the end. You do not need to. The even state is always at least as good as the odd state because you can always drop the last subtracted element from any subsequence that ends in an odd position.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (all subsequences) | O(2^n) | O(n) |
| Two-state DP | O(n) | O(1) |
The brute force approach generates all 2^n subsequences and computes the alternating sum of each. The two-state DP reduces this to a single pass with two variables, which is optimal.
Building blocks
This problem is built on state machine DP, the same fundamental pattern behind the Buy and Sell Stock family. You define a small set of states (here, just two), define transitions between them, and sweep through the input updating each state.
The skeleton is always:
- Define your states and what they represent.
- Write the transition for each state at each step.
- Initialize the states correctly (here, both start at 0).
- Return the appropriate final state.
This pattern generalizes to problems with more states. Best Time to Buy and Sell Stock with Cooldown adds a "cooldown" state. Stock III limits you to two transactions, adding more states. But the mechanics are the same: define states, write transitions, sweep once.
Edge cases
- Single element: the answer is
nums[0]. You pick it at even position 0 and add it. - All equal values: e.g., [3, 3, 3, 3]. The answer is 3. Pick just the first element. Adding and then subtracting equal values gains nothing.
- Strictly decreasing: e.g., [5, 4, 3, 2, 1]. The answer is 5. Just pick the first (largest) element.
- Strictly increasing: e.g., [1, 2, 3, 4, 5]. The answer is 5. Pick just the last element. Or pick [1, 2, 3, 4, 5] for +1 -2 +3 -4 +5 = 3. Actually, picking [5] alone gives 5, which is better.
- Two elements: [a, b]. The answer is
max(a, b, a - b). You either pick a alone, b alone, or both.
From understanding to recall
You have just walked through the two-state DP approach, and the transitions probably make sense right now. But will you remember that even = max(even, odd + num) is the correct update when you see this problem in an interview next month?
Understanding a solution and being able to reproduce it from scratch are different skills. Spaced repetition bridges that gap. You practice writing the two-state transitions from memory at increasing intervals. After a few repetitions, the pattern is automatic. You see "alternating subsequence" or "buy and sell" and the two-variable loop flows out without hesitation.
State machine DP is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.
Related posts
- Best Time to Buy and Sell Stock II - the exact same two-state pattern applied to stock trading
- House Robber - another DP with "take or skip" decisions at each element
- Best Time to Buy and Sell Stock with Cooldown - a more complex state machine DP