Maximum Alternating Subsequence Sum

How it works

Notice that each state only depends on the state at the next index. We do not need the entire DP table; just two variables suffice to track the best even-position sum and odd-position sum for the suffix starting at the current index.

This reduces space from O(n) to O(1) while maintaining the same logic.

Steps

1. Initialize sumEven = 0 and sumOdd = 0.
2. Iterate from i = n-1 down to 0:
   • tmpEven = max(nums[i] + sumOdd, sumEven) represents the best sum if next pick is even.
   • tmpOdd = max(-nums[i] + sumEven, sumOdd) represents the best sum if next pick is odd.
   • Update sumEven = tmpEven and sumOdd = tmpOdd.
3. Return sumEven.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Confusing Subsequence with Subarray

A subsequence does not require elements to be contiguous, while a subarray does. In this problem, you can skip elements freely. For example, from [4, 2, 5, 3], you can pick [4, 2, 5] (indices 0, 1, 2) or [4, 5] (indices 0, 2). Treating this as a subarray problem leads to incorrect answers.

Misunderstanding the Alternating Pattern

The alternating sum starts with addition for the first picked element, then subtracts the second, adds the third, and so on. The pattern is based on the position within the chosen subsequence, not the original array indices. Starting with subtraction or miscounting the parity will produce wrong results.

Integer Overflow

The sum can exceed 32-bit integer limits when the array is large and contains values up to 10^5. Use long in Java/C++ or ensure your language handles big integers. Failing to account for this causes overflow errors on larger test cases.

from typing import List

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        sumEven = sumOdd = 0

        for i in range(len(nums) - 1, -1, -1):
            tmpEven = max(sumOdd + nums[i], sumEven)
            tmpOdd = max(sumEven - nums[i], sumOdd)
            sumEven, sumOdd = tmpEven, tmpOdd

        return sumEven

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        long long sumEven = 0, sumOdd = 0;

        for (int i = nums.size() - 1; i >= 0; i--) {
            long long tmpEven = max(nums[i] + sumOdd, sumEven);
            long long tmpOdd = max(-nums[i] + sumEven, sumOdd);
            sumEven = tmpEven;
            sumOdd = tmpOdd;
        }

        return sumEven;
    }
};