Coding

Maximum Alternating Subarray Sum

Asked at

Amazon

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

func maximumAlternatingSubarraySum(nums []int) int64 {

}

Stuck? Show a way to structure it+

01Define best sums ending at i for both starting signs.
02Extend a prior alternating subarray or start fresh.
03Use the parity of the next sign in each recurrence.
04Update the global maximum.
05Keep only previous states.

Reference answer

Keep two DP values while scanning: plus is the best alternating sum of a non-empty subarray ending here whose current contribution has positive sign, and minus is the analogous value whose current contribution has negative sign. For value x, a positive-ending sequence is either the new subarray x or an earlier negative-ending sequence plus x; a negative-ending sequence is an earlier positive-ending sequence minus x. Save old states before overwriting: newPlus = max(x, oldMinus + x) and newMinus = oldPlus - x when extension exists. Update the answer with newPlus and, if the definition permits it, the appropriate starting-sign state. Explain the exact sign convention before coding. This Kadane-style recurrence is O(N) time and O(1) space.

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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question