# 2036. Maximum Alternating Subarray Sum

## 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

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

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

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

• 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;
}
}

• 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;
}
};

• 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


• 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)
}

• 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;
}