Leetcode 1746. Maximum Subarray Sum After One Operation
Problem Explanation
Given an integer array nums
, you can perform exactly one operation where you can replace one element nums[i]
with nums[i] * nums[i]
. The goal is to find the maximum possible subarray sum after exactly one operation. The subarray must and will be non-empty.
Let's walk through an example to understand the problem statement.
Example
1Input: nums = [1,-1,1,1,-1,-1,1]
For this input, we can replace the element at index 1 (0-indexed) with the square of -1, which is 1. The new array will become: [1, 1, 1, 1, -1, -1, 1]
. Now, the maximum subarray sum is 1 + 1 + 1 + 1 = 4
. So, the output should be 4.
Solution Approach
The solution for this problem involves applying dynamic programming.
We'll keep track of two variables, regular
and squared
. regular
keeps track of the maximum subarray sum for the current element without squaring the numbers, whereas squared
keeps track of the maximum subarray sum when a number in the subarray is squared.
We'll iterate through the input array from left to right, and for each index, we make the following decisions:
-
For the
squared
variable, we choose the maximum value among:- Squaring the current number
- Adding the squared current number to the
regular
variable - Adding the current number to the
squared
variable
-
For the
regular
variable, we choose the maximum value among:- The current number
- Adding the current number to the
regular
variable
Eventually, we find the maximum possible subarray sum and store it in a variable called ans
.
Python Solution
1class Solution:
2 def maxSumAfterOperation(self, nums: List[int]) -> int:
3 ans = float('-inf')
4 regular = 0
5 squared = 0
6
7 for num in nums:
8 squared = max(num * num, regular + num * num, squared + num)
9 regular = max(num, regular + num)
10 ans = max(ans, squared)
11
12 return ans
Java Solution
1class Solution {
2 public int maxSumAfterOperation(int[] nums) {
3 int ans = Integer.MIN_VALUE;
4 int regular = 0;
5 int squared = 0;
6
7 for (int num : nums) {
8 squared = Math.max(Math.max(num * num, regular + num * num), squared + num);
9 regular = Math.max(num, regular + num);
10 ans = Math.max(ans, squared);
11 }
12
13 return ans;
14 }
15}
JavaScript Solution
1class Solution {
2 maxSumAfterOperation(nums) {
3 let ans = Number.MIN_SAFE_INTEGER;
4 let regular = 0;
5 let squared = 0;
6
7 for (const num of nums) {
8 squared = Math.max(num * num, regular + num * num, squared + num);
9 regular = Math.max(num, regular + num);
10 ans = Math.max(ans, squared);
11 }
12
13 return ans;
14 }
15}
C++ Solution
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6 public:
7 int maxSumAfterOperation(vector<int>& nums) {
8 int ans = INT_MIN;
9 int regular = 0;
10 int squared = 0;
11
12 for (const int num : nums) {
13 squared = max({num * num, regular + num * num, squared + num});
14 regular = max(num, regular + num);
15 ans = max(ans, squared);
16 }
17
18 return ans;
19 }
20};
C# Solution
1using System;
2
3public class Solution {
4 public int MaxSumAfterOperation(int[] nums) {
5 int ans = Int32.MinValue;
6 int regular = 0;
7 int squared = 0;
8
9 foreach (int num in nums) {
10 squared = Math.Max(Math.Max(num * num, regular + num * num), squared + num);
11 regular = Math.Max(num, regular + num);
12 ans = Math.Max(ans, squared);
13 }
14
15 return ans;
16 }
17}
Problem Analysis
The problem asks us to find the maximum possible subarray sum after exactly one operation performed on the given integer array.
The operation mentioned in the problem statement involves replacing one element with its square, exactly once. And then, we need to find the maximum subarray sum.
Let's take a look at another example for better understanding.
Example
1Input: nums = [-4,1,-2,-3,1,1,-3]
To get the maximum subarray sum after exactly one operation on this input, we can replace the element at index 5 (0-indexed) with the square of 1, which is 1. The new array will become: [-4, 1, -2, -3, 1, 1, -3]
. Now, the maximum subarray sum is -4 + 1 - 2 + -3 + 1 + 1 = -6
. So, the output should be -6.
Time Complexity Analysis
The time complexity of all the solutions above is O(n) as each of them iterates through the given nums
array exactly once.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.