Skip to content

2036. Maximum Alternating Subarray Sum πŸ”’

DifficultyMedium

Description

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 the maximum alternating subarray sum of any subarray of nums.

 

Example 1:

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:

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:

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 <= 105
  • -105 <= nums[i] <= 105

Solutions

Solution 1: Dynamic Programming

Thinking

We want the maximum alternating subarray sum; \(n \le 10^5\) forbids interval enumeration. Classify by the last sign: the new state depends only on the opposite state of the previous index.

\(f\) ends with \(+\textit{nums}[i]\), \(g\) with \(-\textit{nums}[i]\). New \(f\) continues \(g\) or starts fresh; \(g\) continues the just-updated \(f\).

Roll both in \(O(1)\) space and take the global max.

We define \(f\) as the maximum sum of the alternating subarray ending with \(\textit{nums}[i]\), and define \(g\) as the maximum sum of the alternating subarray ending with \(-\textit{nums}[i]\). Initially, both \(f\) and \(g\) are \(-\infty\).

Next, we traverse the array \(\textit{nums}\). For position \(i\), we need to maintain the values of \(f\) and \(g\), i.e., \(f = \max(g, 0) + \textit{nums}[i]\), and \(g = f - \textit{nums}[i]\). The answer is the maximum value among all \(f\) and \(g\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
class Solution:
    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:
        ans = f = g = -inf
        for x in nums:
            f, g = max(g, 0) + x, f - x
            ans = max(ans, f, g)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public long maximumAlternatingSubarraySum(int[] nums) {
        final long inf = 1L << 60;
        long ans = -inf, f = -inf, g = -inf;
        for (int x : nums) {
            long ff = Math.max(g, 0) + x;
            g = f - x;
            f = ff;
            ans = Math.max(ans, Math.max(f, g));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    long long maximumAlternatingSubarraySum(vector<int>& nums) {
        using ll = long long;
        const ll inf = 1LL << 60;
        ll ans = -inf, f = -inf, g = -inf;
        for (int x : nums) {
            ll ff = max(g, 0LL) + x;
            g = f - x;
            f = ff;
            ans = max({ans, f, g});
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
func maximumAlternatingSubarraySum(nums []int) int64 {
    const inf = 1 << 60
    ans, f, g := -inf, -inf, -inf
    for _, x := range nums {
        f, g = max(g, 0)+x, f-x
        ans = max(ans, max(f, g))
    }
    return int64(ans)
}

1
2
3
4
5
6
7
8
function maximumAlternatingSubarraySum(nums: number[]): number {
    let [ans, f, g] = [-Infinity, -Infinity, -Infinity];
    for (const x of nums) {
        [f, g] = [Math.max(g, 0) + x, f - x];
        ans = Math.max(ans, f, g);
    }
    return ans;
}

Comments