Maximum Subarray Sum After One Operation
AmazonThe 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)
{
}
}go
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
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
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.
Next question