486. Maximum Subarray Sum After One Operation

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.

Example 1:

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.

Example 2:

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.

Now Your Turn!

Pick the correct output for the given input

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

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

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

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

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

Input:

Nums