LeetCode 1911 - Maximum Alternating Subsequence Sum

LeetCode Problem 1911

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to compute the maximum possible alternating sum of any subsequence of the given array.

An alternating sum is calculated after the chosen subsequence is reindexed starting from index 0. Elements at even positions in the subsequence are added, while elements at odd positions are subtracted.

For example, if we choose the subsequence [4,2,5], then:

• Index 0: +4
• Index 1: -2
• Index 2: +5

The alternating sum becomes:

4 - 2 + 5 = 7

The important detail is that the subsequence is reindexed after selection. The original indices in nums do not matter once the subsequence is formed. Only the order of elements must remain the same.

The input consists of:

• nums, an array of positive integers
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

The constraints are large enough that exponential or quadratic solutions will not work efficiently. Any practical solution must run in linear time or close to it.

Because all numbers are positive, several interesting behaviors emerge:

• Sometimes it is best to keep only one large number.
• Sometimes alternating between gains and losses creates a larger total.
• The optimal subsequence is not necessarily contiguous.

Several edge cases are important:

• Arrays with a single element
• Strictly increasing arrays
• Strictly decreasing arrays
• Arrays where skipping many elements is optimal
• Very large arrays requiring efficient memory usage

The problem guarantees at least one element, so we never need to handle an empty input array.

Approaches

Brute Force Approach

A brute force solution would generate every possible subsequence of the array. For each subsequence, we would compute its alternating sum and track the maximum value found.

For an array of length n, there are 2^n possible subsequences. Computing the alternating sum for each subsequence may take up to O(n) time.

This guarantees correctness because every valid subsequence is examined. However, it is completely impractical for n = 10^5.

Even for n = 30, the number of subsequences already exceeds one billion.

Key Insight for the Optimal Solution

The key observation is that at every position we only care about two states:

• The best alternating sum where the current subsequence length is even
• The best alternating sum where the current subsequence length is odd

Another way to think about this is:

• even represents the best value when the next chosen number would be subtracted
• odd represents the best value when the next chosen number would be added

When processing a new number num, we have two choices:

• Skip it
• Include it in the subsequence

If we include it:

• Adding num to an even-length subsequence creates an odd-length subsequence
• Subtracting num from an odd-length subsequence creates an even-length subsequence

This naturally leads to a dynamic programming transition with only constant memory.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × 2^n)	O(n)	Enumerates all subsequences
Optimal Dynamic Programming	O(n)	O(1)	Tracks only two DP states

Algorithm Walkthrough

1. Initialize two variables:

• even = 0
• odd = 0

Here:

• even stores the best alternating sum for a subsequence with even length
• odd stores the best alternating sum for a subsequence with odd length

2. Iterate through each number num in nums.
3. Compute the new value for odd.

If we include num as the next element after an even-length subsequence, it will be added:

even + num

We also have the option to skip num, so:

new_odd = max(odd, even + num)

4. Compute the new value for even.

If we include num after an odd-length subsequence, it will be subtracted:

odd - num

We may also skip the number:

new_even = max(even, odd - num)

5. Update both states simultaneously.
6. Continue until all elements are processed.
7. Return odd.

The final answer is always stored in odd because a subsequence contributing positively starts with an addition.

Why it works

The algorithm maintains a dynamic programming invariant:

• odd always stores the maximum alternating sum achievable using processed elements where the subsequence length is odd.
• even always stores the maximum alternating sum achievable using processed elements where the subsequence length is even.

At every step, the algorithm considers both possibilities, taking or skipping the current number, and preserves the best achievable values. Since every valid subsequence can be represented through these transitions, the final odd value is guaranteed to be optimal.

Python Solution

from typing import List

class Solution:

    def maxAlternatingSum(self, nums: List[int]) -> int:
        even = 0
        odd = 0

        for num in nums:
            new_odd = max(odd, even + num)
            new_even = max(even, odd - num)

            odd = new_odd
            even = new_even

        return odd

The implementation directly follows the dynamic programming formulation.

The variables odd and even store the best results for the two possible subsequence parity states.

For every number:

• new_odd represents the best odd-length subsequence after processing the current number.
• new_even represents the best even-length subsequence after processing the current number.

The transition considers both choices:

• Skip the current number
• Include the current number

Using temporary variables is important because both updates depend on the previous iteration's values.

The algorithm processes the array exactly once and uses only constant extra space.

Go Solution

func maxAlternatingSum(nums []int) int64 {
    var even int64 = 0
    var odd int64 = 0

    for _, num := range nums {
        value := int64(num)

        newOdd := max64(odd, even+value)
        newEven := max64(even, odd-value)

        odd = newOdd
        even = newEven
    }

    return odd
}

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

The Go implementation mirrors the Python solution closely.

One important difference is the use of int64. The problem constraints allow sums that may exceed the standard 32-bit integer range, so using int64 ensures correctness.

Go does not provide a built-in max function for integers, so a helper function max64 is implemented.

The function safely handles all valid inputs, including arrays with a single element.

Worked Examples

Example 1

Input:

nums = [4,2,5,3]

Initial state:

Step	num	odd	even
Start	-	0	0

Processing 4:

new_odd = max(0, 0 + 4) = 4
new_even = max(0, 0 - 4) = 0

Step	num	odd	even
1	4	4	0

Processing 2:

new_odd = max(4, 0 + 2) = 4
new_even = max(0, 4 - 2) = 2

Step	num	odd	even
2	2	4	2

Processing 5:

new_odd = max(4, 2 + 5) = 7
new_even = max(2, 4 - 5) = 2

Step	num	odd	even
3	5	7	2

Processing 3:

new_odd = max(7, 2 + 3) = 7
new_even = max(2, 7 - 3) = 4

Step	num	odd	even
4	3	7	4

Final answer:

7

Example 2

Input:

nums = [5,6,7,8]

Step	num	odd	even
Start	-	0	0
1	5	5	0
2	6	6	0
3	7	7	0
4	8	8	0

The best strategy is selecting only [8].

Final answer:

8

Example 3

Input:

nums = [6,2,1,2,4,5]

Step	num	odd	even
Start	-	0	0
1	6	6	0
2	2	6	4
3	1	6	5
4	2	7	5
5	4	9	5
6	5	10	5

Final answer:

10

The optimal subsequence is:

[6,1,5]

Alternating sum:

6 - 1 + 5 = 10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only two DP variables are maintained

The algorithm performs a constant amount of work for every element in the array. No nested loops or auxiliary data structures are used.

Memory usage remains constant regardless of input size because only two state variables are tracked throughout execution.

Test Cases

from typing import List

class Solution:

    def maxAlternatingSum(self, nums: List[int]) -> int:
        even = 0
        odd = 0

        for num in nums:
            new_odd = max(odd, even + num)
            new_even = max(even, odd - num)

            odd = new_odd
            even = new_even

        return odd

solution = Solution()

assert solution.maxAlternatingSum([4,2,5,3]) == 7  # provided example 1
assert solution.maxAlternatingSum([5,6,7,8]) == 8  # provided example 2
assert solution.maxAlternatingSum([6,2,1,2,4,5]) == 10  # provided example 3

assert solution.maxAlternatingSum([1]) == 1  # single element
assert solution.maxAlternatingSum([10]) == 10  # single large element

assert solution.maxAlternatingSum([1,2,3,4,5]) == 5  # increasing sequence
assert solution.maxAlternatingSum([5,4,3,2,1]) == 5  # decreasing sequence

assert solution.maxAlternatingSum([1,100,1]) == 100  # best to take only one element
assert solution.maxAlternatingSum([3,1,4]) == 6  # choose [3,1,4]

assert solution.maxAlternatingSum([2,2,2,2]) == 2  # repeated equal values
assert solution.maxAlternatingSum([1,5,2,10]) == 14  # choose [1,2,10]

assert solution.maxAlternatingSum([100000] * 1000) == 100000  # large repeated values

Test	Why
[4,2,5,3]	Validates standard alternating behavior
[5,6,7,8]	Validates choosing a single maximum element
[6,2,1,2,4,5]	Validates skipping intermediate values
[1]	Smallest valid input
[10]	Single large element
[1,2,3,4,5]	Increasing sequence behavior
[5,4,3,2,1]	Decreasing sequence behavior
[1,100,1]	Confirms skipping small surrounding values
[3,1,4]	Validates alternating accumulation
[2,2,2,2]	Repeated equal values
[1,5,2,10]	Tests multiple profitable transitions
[100000] * 1000	Large-value stress case

Edge Cases

One important edge case is a single-element array. Since the subsequence can contain just one number, the answer must simply be that element itself. A buggy implementation might incorrectly initialize states and return zero instead. The current implementation handles this naturally because the first iteration updates odd to the element value.

Another important edge case is a strictly increasing array such as [1,2,3,4,5]. A naive greedy strategy might attempt to include many elements, but subtracting intermediate values can reduce the total gain. The dynamic programming transitions correctly evaluate whether taking or skipping each value produces the best result.

A third edge case is arrays where the optimal solution skips most elements, such as [1,100,1]. Including the surrounding 1s would lower the alternating sum. The algorithm correctly preserves the best previous state through the max operation, allowing it to ignore harmful choices.

Another subtle edge case involves repeated equal values like [2,2,2,2]. Multiple subsequences produce the same result, and the implementation must avoid accidentally degrading the state through unnecessary transitions. Since each update always compares against the existing state, the optimal value is preserved correctly.

Finally, very large arrays require efficient memory usage. Since the constraints allow up to 10^5 elements, storing large DP tables would be unnecessary overhead. The implementation uses only two variables, ensuring constant extra space regardless of input size.