跳转至

2036. 最大交替子数组和 🔒

题目描述

子数组是以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

解法

方法一：动态规划

思考

交替子数组要求和 \(\sum (-1)^{k} a_{i+k}\) 最大，\(n \le 10^5\) 不能枚举区间。以右端分类：最后一项带正号或带负号，转移只依赖前一位置的相反状态。

\(f\) 表示以 \(+nums[i]\) 结尾的最大和，\(g\) 表示以 \(-nums[i]\) 结尾。新的 \(f\) 可接在旧 \(g\) 后或单独成段，\(g\) 则接在刚算出的 \(f\) 上（相当于给上一项改号）。

全程 \(O(1)\) 空间滚动，答案为所有 \(f,g\) 的最大。

我们定义 \(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)\)。

1
2
3
4
5
6
7
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

1
2
3
4
5
6
7
8
9
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)
}

1
2
3
4
5
6
7
8
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;
}

评论