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

All Problems

All Solutions