Welcome to Subscribe On Youtube
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;
}
};