⚡Flashcard Drill➔
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

  1. Process elements left to right, tracking two states: even, the best alternating sum of an even-length subsequence, and odd, the best of an odd-length one.
  2. Appending an element flips the parity: extending an even-length subsequence makes the new element even-indexed and adds it.
  3. Extending an odd-length subsequence makes the new element odd-indexed and subtracts it.
  4. The transitions are new_odd = max(odd, even + x) and new_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: even must use the previous odd, so compute both from the old values first.
  • Seeding odd with 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 even at 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems