Coding

Maximum Subarray Sum After One Operation

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given an integer array nums. You can replace at most one element in nums with nums[i]*nums[i]. Return the maximum possible sum of a non-empty subarray after performing at most one such operation. A subarray is a contiguous sequence of elements within an array.

Input: nums = [2,-1,-4,-3] **Output: **17 Explanation: You can perform the operation on index 2 (0-indexed) to make nums = [2,-1,16,-3]. Now, the maximum subarray sum is 2 + -1 + 16 = 17.

Input: nums = [1,-1,1,1,-1,-1,1] Output: 4 Explanation: You can perform the operation on index 1 (0-indexed) to make nums = [1,1,1,1,-1,-1,1]. Now, the maximum subarray sum is 1 + 1 + 1 + 1 = 4.

Input: nums = [-2,3,-1,5,-4]

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

cpp

class Solution {
public:
    int maxSumAfterOperation(vector<int>& nums) {
       //Your Code Goes Here 
    }
};

java

class Solution {
    public int maxSumAfterOperation(int[] nums) {
       
    }
}

python

class Solution:
    def maxSumAfterOperation(self, nums):

javascript

class Solution {
    maxSumAfterOperation(nums) {
      
    }
}

csharp

class Solution
{
    public int MaxSumAfterOperation(int[] nums)
    {
        
    }
}

func maxSumAfterOperation(nums []int) int {
    //your code goes here
}

Stuck? Show a way to structure it+

01Track best subarray ending here without the operation.
02Track best ending here with the operation used.
03Either start, extend normally, or apply the operation now.
04Update both states from old values.
05Keep the global best.

Reference answer

For the common operation x -> x*x, maintain plain, the best sum of a non-empty subarray ending at the previous index without applying the operation, and used, the best sum ending there with it already applied. At value x, compute newUsed = max(x*x, plain + x*x, used + x): start with the operated value, apply the operation after a plain prefix, or extend an already-operated prefix. Compute newPlain = max(x, plain + x). Update the answer with newUsed, saving old values before assignment. This enumerates all placements of the one operation without a nested loop. It is O(N) time and O(1) space. Confirm the exact operation from the prompt, then substitute its transformed value in the recurrence.

Then expect these follow-ups

How would you allow at most two operations?
Tests: state expansion
How would you return the selected range?
Tests: reconstruction

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