Code Implementation

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

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

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

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

Problem Description

You are given an array of integers nums. You want to select a non-empty subarray (contiguous elements) and calculate its alternating sum. The alternating sum is defined as the sum of elements at even indices minus the sum of elements at odd indices in the subarray (with 0-based indexing).

Formally, for a subarray nums[i..j], the alternating sum is:
nums[i] - nums[i+1] + nums[i+2] - nums[i+3] + ...

Your task is to return the maximum alternating sum among all possible non-empty subarrays of nums.

• Each element can be used at most once (no reusing elements).
• Subarrays must be contiguous.
• There is guaranteed to be at least one valid subarray.

Thought Process

At first glance, the problem seems similar to finding the maximum sum subarray (Kadane's Algorithm), but with the twist that we alternate adding and subtracting elements. This means the order and position (even or odd) of each element in the chosen subarray matters.

A brute-force solution would be to check all possible subarrays, calculate their alternating sum, and return the maximum. However, this is inefficient for large arrays because the number of subarrays is O(n²).

To optimize, we can notice that for any prefix ending at index i, we can track two states:

• even: the maximum alternating sum ending at i where nums[i] is at an even position in the subarray
• odd: the maximum alternating sum ending at i where nums[i] is at an odd position in the subarray

Solution Approach

• State Variables:
  • even: The maximum alternating sum for subarrays ending with an even position (i.e., the last element is added).
  • odd: The maximum alternating sum for subarrays ending with an odd position (i.e., the last element is subtracted).
• Initialization:
  • Start with even = 0 and odd = 0.
• Transition:
  • For each num in nums:
    • To get a new even sum, either keep the previous even (don't include num), or take odd + num (add num as the next even-positioned element).
    • To get a new odd sum, either keep the previous odd (don't include num), or take even - num (subtract num as the next odd-positioned element).
• Result:
  • After processing all elements, even will hold the maximum alternating sum.
• Why does this work?
  • At each step, we consider both possibilities: extending a previous subarray or starting fresh from the current element, and always keep the best outcome for both even and odd cases.

Example Walkthrough

Let's use the input nums = [4,2,5,3].

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

The maximum alternating sum is 7, achieved by subarray [4,2,5] (4 - 2 + 5 = 7).

Time and Space Complexity

• Brute-force approach:
  • We would check all O(n²) subarrays, and for each, calculate the alternating sum in O(n) time, for a total of O(n³).
• Optimized DP approach:
  • We process each element once, with constant-time updates. So, the time complexity is O(n).
  • We only use two variables (even and odd), so the space complexity is O(1).

Summary

The key insight is to model the problem using dynamic programming with two states, tracking the best possible alternating sum for even and odd positions as we iterate through the array. This approach efficiently computes the maximum alternating sum in linear time, making it both elegant and practical for large inputs.