README.md

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

解法

方法一：动态规划

定义状态 $a$ 表示以当前元素作为正结尾的最大交替子数组和，状态 $b$ 表示以当前元素作为负结尾的最大交替子数组和。初始时 $a = nums[0]$，$b = -\infty$。

遍历数组，对于当前元素 $nums[i]$，有

$$ \begin{aligned} a = \max(nums[i], b + nums[i]) \\ b = a - nums[i] \end{aligned} $$

求出 $a$ 和 $b$ 后，将 $a$ 和 $b$ 中的最大值与当前最大交替子数组和进行比较，更新最大交替子数组和。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组长度。

Python3

class Solution:
    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:
        ans = nums[0]
        a, b = nums[0], -inf
        for v in nums[1:]:
            a, b = max(v, b + v), a - v
            ans = max(ans, a, b)
        return ans

Java

class Solution {
    public long maximumAlternatingSubarraySum(int[] nums) {
        long ans = nums[0];
        long a = nums[0], b = -(1 << 30);
        for (int i = 1; i < nums.length; ++i) {
            long c = a, d = b;
            a = Math.max(nums[i], d + nums[i]);
            b = c - nums[i];
            ans = Math.max(ans, Math.max(a, b));
        }
        return ans;
    }
}

C++

using ll = long long;

class Solution {
public:
    long long maximumAlternatingSubarraySum(vector<int>& nums) {
        ll ans = nums[0];
        ll a = nums[0], b = -(1 << 30);
        for (int i = 1; i < nums.size(); ++i) {
            ll c = a, d = b;
            a = max(1ll * nums[i], d + nums[i]);
            b = c - nums[i];
            ans = max(ans, max(a, b));
        }
        return ans;
    }
};

Go

func maximumAlternatingSubarraySum(nums []int) int64 {
	ans := nums[0]
	a, b := nums[0], -(1 << 30)
	for _, v := range nums[1:] {
		c, d := a, b
		a = max(v, d+v)
		b = c - v
		ans = max(ans, max(a, b))
	}
	return int64(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...