Problem Description

Given an array of positive integers nums, you are to select a subsequence (not necessarily contiguous) where the sum of the elements taken at odd indices of the subsequence is subtracted by the sum of the elements taken at even indices (using 1-based indexing within the subsequence). The goal is to maximize this alternating sum.

Formally, for a subsequence seq of nums, the alternating sum is defined as:

seq[0] - seq[1] + seq[2] - seq[3] + ...

Return the maximum possible alternating sum of any subsequence of nums.

• Each element in nums can be used at most once.
• The subsequence must maintain the original order of elements.
• There is always at least one valid solution.

Thought Process

At first glance, it seems like we might need to check all possible subsequences, compute the alternating sum for each, and keep track of the maximum. This brute-force approach, however, is infeasible for larger arrays due to the exponential number of subsequences.

To optimize, we notice that the alternating sum depends on the relative positions (odd/even) within the chosen subsequence, not the original array. We can use dynamic programming to keep track of two states as we iterate:

• even: The maximum alternating sum for subsequences ending at an even position (1st, 3rd, 5th, ...).
• odd: The maximum alternating sum for subsequences ending at an odd position (2nd, 4th, 6th, ...).

At each step, we decide whether to include the current number in the subsequence (and at which position), or to skip it.

Solution Approach

We use dynamic programming with two variables to track the best possible sums:

1. Initialize:
   • even = 0 (no numbers chosen yet, so sum is 0)
   • odd = 0 (no numbers chosen yet, so sum is 0)
2. Iterate through nums:
   • For each number x in nums:
     • If we pick x as the next odd index in the subsequence, our alternating sum increases by x (since it's the turn to add), so update even = max(even, odd + x).
     • If we pick x as the next even index, our alternating sum decreases by x (since it's the turn to subtract), so update odd = max(odd, even - x).
     • At each step, we keep the maximum value for both states.
3. Result:
   • The answer is the value of even after processing the entire array.

This approach is efficient because it only needs to keep track of two variables and updates them in constant time for each element.

Example Walkthrough

Let's use nums = [4, 2, 5, 3] as an example.

• Start: even = 0, odd = 0
• First element (4):
  • even = max(0, 0 + 4) = 4
  • odd = max(0, 0 - 4) = 0
• Second element (2):
  • even = max(4, 0 + 2) = 4
  • odd = max(0, 4 - 2) = 2
• Third element (5):
  • even = max(4, 2 + 5) = 7
  • odd = max(2, 4 - 5) = 2
• Fourth element (3):
  • even = max(7, 2 + 3) = 7
  • odd = max(2, 7 - 3) = 4

The answer is even = 7. The subsequence [4, 5, 3] gives 4 - 5 + 3 = 2, but [4, 5] gives 4 - 5 = -1, [4, 5, 3] gives 4 - 5 + 3 = 2, [4, 2, 5] gives 4 - 2 + 5 = 7, which is the maximum.

Time and Space Complexity

• Brute-force Approach:
  • There are 2ⁿ possible subsequences, and calculating the alternating sum for each takes O(n) time.
  • Time Complexity: O(n × 2ⁿ)
  • Space Complexity: O(n) for recursion stack or storing subsequences.
• Optimized Dynamic Programming Approach:
  • We only make a single pass through the array, updating two variables.
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Summary

The Maximum Alternating Subsequence Sum problem can be solved efficiently using a simple dynamic programming approach that tracks the best possible alternating sum for subsequences ending at even and odd positions. By updating two variables as we iterate, we avoid the exponential complexity of brute-force and achieve a linear time, constant space solution. The key insight is recognizing the alternating nature of the sum and using state variables to represent the two possible "parities" of the subsequence's length.

Code Implementation

class Solution:
    def maxAlternatingSum(self, nums):
        even = 0
        odd = 0
        for x in nums:
            even = max(even, odd + x)
            odd = max(odd, even - x)
        return even
      

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        long long even = 0, odd = 0;
        for (int x : nums) {
            long long new_even = max(even, odd + x);
            long long new_odd = max(odd, even - x);
            even = new_even;
            odd = new_odd;
        }
        return even;
    }
};
      

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long even = 0, odd = 0;
        for (int x : nums) {
            long newEven = Math.max(even, odd + x);
            long newOdd = Math.max(odd, even - x);
            even = newEven;
            odd = newOdd;
        }
        return even;
    }
}
      

var maxAlternatingSum = function(nums) {
    let even = 0, odd = 0;
    for (let x of nums) {
        let newEven = Math.max(even, odd + x);
        let newOdd = Math.max(odd, even - x);
        even = newEven;
        odd = newOdd;
    }
    return even;
};