Formatted question description: https://leetcode.ca/all/2036.html

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

## Examples:

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

## Solution:

Logical Thinking

We can divide this problem into two dynamic programming sub-problems: Firstly, if we negate the elements with odd indices, then the problem becomes to find the maximum subarray sum from 0 to n; Secondly, if we negate the elements with even indices, the problem becomes to find the maximum subarray sum from 1 to n. For each sub-problem, we can use Kadane's Algorithm to solve it, and the answer is the maximum of two sub-optimum.

C++

//  Topic   ：2036. Maximum Alternating Subarray Sum (https://leetcode.com/problems/maximum-alternating-subarray-sum/)
//  Time    : O(N)
//  Space   : O(N)

class Solution {
public:
long long maximumAlternatingSubarraySum(vector<int>& nums) {
long long ans = nums[0], sum1 = nums[0], sum2 = 0, n = nums.size();
for (int i = 1; i < n; i++)
{
if (i % 2 == 0)
{
if (sum1 + nums[i] > nums[i])
sum1 += nums[i];
else
sum1 = nums[i];
sum2 -= nums[i];
}
else
{
sum1 -= nums[i];
if (sum2 + nums[i] > nums[i])
sum2 += nums[i];
else
sum2 = nums[i];
}
ans = max<long long>(ans, sum1);
ans = max<long long>(ans, sum2);
}
return ans;
}
};