Question

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

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

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