Question

2036. 最大交替子数组和

English Version

题目描述

子数组是以0下标开始的数组的连续非空子序列，从 i 到 j（0 <= i <= j < nums.length）的 子数组交替和 被定义为 nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j] 。

给定一个以0下标开始的整数数组nums，返回它所有可能的交替子数组和的最大值。

 

示例 1：

输入：nums = [3,-1,1,2]
输出：5
解释：
子数组 [3,-1,1]有最大的交替子数组和3 - (-1) + 1 = 5.

示例 2：

输入：nums = [2,2,2,2,2]
输出：2
解释：
子数组 [2], [2,2,2]和 [2,2,2,2,2]有相同的最大交替子数组和为2
[2]: 2.
[2,2,2]: 2 - 2 + 2 = 2.
[2,2,2,2,2]: 2 - 2 + 2 - 2 + 2 = 2.

示例 3：

输入：nums = [1]
输出：1
解释：
仅有一个非空子数组，为 [1]，它的交替子数组和为 1

 

提示：

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105

解法

方法一：动态规划

我们定义 $f$ 表示以 $nums[i]$ 结尾的交替子数组的最大和，定义 $g$ 表示以 $-nums[i]$ 结尾的交替子数组的最大和，初始时 $f$ 和 $g$ 均为 $-\infty$。

接下来，我们遍历数组 $nums$，对于位置 $i$，我们需要维护 $f$ 和 $g$ 的值，即 $f = \max(g, 0) + nums[i]$，而 $g = f - nums[i]$。答案即为所有 $f$ 和 $g$ 中的最大值。

时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $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;
}