NeetCode #731LC-1911Medium2-D Dynamic Programming
← Back to All Problems#731 · #1911 · Maximum Alternating Subsequence Sum(最大交替子序列和)
📌 Problem Statement & Constraints
Given an array
nums, the alternating sum of a subsequence is the sum of its elements at even indices minus the sum of those at odd indices (0-indexed). Return the maximum alternating sum over all subsequences. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^5.💡 Core Algorithmic Approaches
- Process elements left to right, tracking two states:
even, the best alternating sum of an even-length subsequence, andodd, the best of an odd-length one. - Appending an element flips the parity: extending an even-length subsequence makes the new element even-indexed and adds it.
- Extending an odd-length subsequence makes the new element odd-indexed and subtracts it.
- The transitions are
new_odd = max(odd, even + x)andnew_even = max(even, odd - x), both computed from the previous states.
💻 Benchmark Python3 Implementation
class Solution:
def maxAlternatingSum(self, nums: List[int]) -> int:
even = 0 # best sum with an even-length subsequence
odd = float("-inf") # best sum with an odd-length subsequence
for x in nums:
new_even = max(even, odd - x)
new_odd = max(odd, even + x)
even, odd = new_even, new_odd
return max(even, odd)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): two state variables.
⚠️ Interview Pitfalls & Follow-ups
- Updating the states in place:
evenmust use the previousodd, so compute both from the old values first. - Seeding
oddwith 0: an odd-length subsequence cannot be empty, so it starts at negative infinity. - Misassigning the signs: an element at an even index is added, and at an odd index subtracted.
- Disallowing the empty subsequence: starting
evenat 0 covers it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.