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:

1. 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

2. 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.