MediumDpAI interview only
Maximum Subarray Sum After One Operation
Asked atamazongooglemicrosoft
01 · Problem
You are given an integer array nums. You must perform exactly one operation: choose one index i and replace nums[i] with nums[i] * nums[i].
After the operation, return the maximum possible sum of a non-empty contiguous subarray. The chosen subarray does not have to contain the squared element.
02 · Examples
Example 01
Input
nums = [1,-5,2,3]
Output
31
Square -5 to get [1,25,2,3]. The whole array sums to 1 + 25 + 2 + 3 = 31.
Example 02
Input
nums = [-2,-3]
Output
9
Square -3 to get [-2,9]. The best subarray is [9].
Example 03
Input
nums = [3,-1,2]
Output
10
Square 3 to get [9,-1,2]. The subarray [9,-1,2] sums to 10.
03 · Constraints
- 011 <= nums.length <= 105
- 02-104 <= nums[i] <= 104
- 03Exactly one element must be replaced with its square
- 04The chosen subarray must be non-empty
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.