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