Maximum Alternating Subarray Sum

Problem

A subarray of a 0-indexed integer array is a contiguous non-empty sequence of elements within an array.

The alternating subarray sum of a subarray that ranges from index i to j (inclusive , 0 <= i <= j < nums.length) is nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j].

Given a 0-indexed integer array nums, return _themaximum alternating subarray sum of any subarray of _nums.

Examples

Example 1:

1
2
3
4
5


Input: nums = [3,-1,1,2]
Output: 5
Explanation:
The subarray [3,-1,1] has the largest alternating subarray sum.
The alternating subarray sum is 3 - (-1) + 1 = 5.

Example 2:

1
2
3
4
5
6
7


Input: nums = [2,2,2,2,2]
Output: 2
Explanation:
The subarrays [2], [2,2,2], and [2,2,2,2,2] have the largest alternating subarray sum.
The alternating subarray sum of [2] is 2.
The alternating subarray sum of [2,2,2] is 2 - 2 + 2 = 2.
The alternating subarray sum of [2,2,2,2,2] is 2 - 2 + 2 - 2 + 2 = 2.

Example 3:

1
2
3
4
5


Input: nums = [1]
Output: 1
Explanation:
There is only one non-empty subarray, which is [1].
The alternating subarray sum is 1.

Constraints:

1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5

Solution

Method 1 – Dynamic Programming (Kadane’s Variant)

Intuition

The alternating subarray sum can be seen as a subarray where we alternate between adding and subtracting elements. We can use a dynamic programming approach similar to Kadane’s algorithm, but we need to track two states: the maximum sum ending at the current index with a plus or minus sign.

Approach

Use two variables for each index:
- even: max alternating sum ending at index i with a plus sign (even length from start of subarray).
- odd: max alternating sum ending at index i with a minus sign (odd length from start of subarray).
For each element:
- Update even as the max of current number and odd + nums[i].
- Update odd as the max of even - nums[i].
Track the maximum value of even at each step.
Return the maximum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func maximumAlternatingSubarraySum(nums []int) int64 {
    even, odd := int64(0), int64(-1<<63)
    ans := int64(-1<<63)
    for _, x := range nums {
        newEven := max(int64(x), odd+int64(x))
        newOdd := even - int64(x)
        even, odd = newEven, newOdd
        if even > ans {
            ans = even
        }
    }
    return ans
}
func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
    fun maximumAlternatingSubarraySum(nums: IntArray): Long {
        var even = 0L
        var odd = Long.MIN_VALUE
        var ans = Long.MIN_VALUE
        for (x in nums) {
            val newEven = maxOf(x.toLong(), odd + x)
            val newOdd = even - x
            even = newEven
            odd = newOdd
            ans = maxOf(ans, even)
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def maximumAlternatingSubarraySum(self, nums: list[int]) -> int:
        even: int = 0
        odd: int = float('-inf')
        ans: int = float('-inf')
        for x in nums:
            new_even = max(x, odd + x)
            new_odd = even - x
            even, odd = new_even, new_odd
            ans = max(ans, even)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


impl Solution {
    pub fn maximum_alternating_subarray_sum(nums: Vec<i32>) -> i64 {
        let mut even = 0i64;
        let mut odd = i64::MIN;
        let mut ans = i64::MIN;
        for &x in &nums {
            let new_even = (x as i64).max(odd + x as i64);
            let new_odd = even - x as i64;
            even = new_even;
            odd = new_odd;
            ans = ans.max(even);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    maximumAlternatingSubarraySum(nums: number[]): number {
        let even = 0, odd = -Infinity, ans = -Infinity;
        for (const x of nums) {
            const newEven = Math.max(x, odd + x);
            const newOdd = even - x;
            even = newEven;
            odd = newOdd;
            ans = Math.max(ans, even);
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n), since we process each element once.
🧺 Space complexity: O(1), only a constant number of variables are used.

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming (Kadane’s Variant)#

Intuition#

Approach#

Code#

Complexity#