Skip to content

Latest commit

 

History

History
139 lines (110 loc) · 3.44 KB

File metadata and controls

139 lines (110 loc) · 3.44 KB

中文文档

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

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
}

...