← All questions
Coding

Maximum Alternating Subarray Sum

Asked atAmazon
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

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.

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.

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.

Consider the array nums = [5, -3, 7, -2]. What is the maximum alternating subarray sum?

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105

cpp

class Solution {
public:
    long long maximumAlternatingSubarraySum(vector<int>& nums) {
        // Your code goes here
    }
};

java

class Solution {
    public long maximumAlternatingSubarraySum(int[] nums) {
        // Your code goes here
    }
}

python

class Solution:
    def maximumAlternatingSubarraySum(self, nums):
        # Your code goes here

javascript

class Solution {
    maximumAlternatingSubarraySum(nums) {
        // Your code goes here
    }
}

csharp

class Solution {
    public long MaximumAlternatingSubarraySum(int[] nums) {
        // Write your code here
    }
}

go

func maximumAlternatingSubarraySum(nums []int) int64 {

}
Stuck? Show a way to structure it+
  1. 01Define best sums ending at i for both starting signs.
  2. 02Extend a prior alternating subarray or start fresh.
  3. 03Use the parity of the next sign in each recurrence.
  4. 04Update the global maximum.
  5. 05Keep only previous states.

Reference answer

Then expect these follow-ups

  • How would you return the subarray boundaries?

    Tests: reconstruction

  • What changes if either starting sign is allowed?

    Tests: state coverage

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with EnzoSign up free

Next question