LeetCode 2036. Maximum Alternating Subarray Sum Solution in Java, C++, Python & More | Explanation + Code

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

Solution 1: Dynamic Programming

We define f as the maximum sum of the alternating subarray ending with nums[i], and define g as the maximum sum of the alternating subarray ending with -nums[i]. Initially, both f and g are -∞.

Next, we traverse the array nums. For position i, we need to maintain the values of f and g, i.e., f = max(g, 0) + nums[i], and g = f - nums[i]. The answer is the maximum value among all f and g.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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) }(code-box)

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; }(code-box)