# Maximum Subarray Sum After One Operation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-subarray-sum-after-one-operation)
Canonical: https://scaleengineer.com/dsa/problems/maximum-subarray-sum-after-one-operation
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
\[Fetch error\]

# Approaches
## Brute Force
This approach exhaustively checks every possible contiguous subarray. For each subarray, it calculates two potential maximums: the sum of the subarray as is, and the sum after squaring one of its elements. By trying to square every element in every subarray, it guarantees finding the maximum possible sum, but at a very high computational cost.
**Time:** O(N^3), where N is the length of the input array. The three nested loops for `i`, `j`, and `k` lead to cubic complexity. · **Space:** O(1), as it only uses a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Correct for all inputs, given enough time.
**Cons:** Highly inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for medium to large inputs.
### Explanation
The brute-force method systematically explores all possibilities. It uses two nested loops to generate all possible start and end points for a subarray. For each of these subarrays, it first calculates the standard sum. Then, a third loop iterates through the elements of the current subarray, and for each element, it calculates what the subarray sum would be if that specific element were squared. The global maximum sum is updated whenever a larger sum is found.

Here is an optimized version of the brute-force approach that reduces the complexity from O(N^4) to O(N^3) by calculating the subarray sum incrementally.

```java
class Solution {
    public int maxSumAfterOperation(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;

        // If all numbers are negative, the result is the square of the largest number (least negative)
        // or the largest number itself. The loop below handles this, but this is a good edge case to consider.
        // For example, for [-1, -100], max is (-1)^2=1, not -1.

        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                
                // Case 1: No operation on subarray nums[i...j]
                maxSum = Math.max(maxSum, currentSum);
                
                // Case 2: One operation on an element within nums[i...j]
                for (int k = i; k <= j; k++) {
                    int sumWithOp = currentSum - nums[k] + (nums[k] * nums[k]);
                    maxSum = Math.max(maxSum, sumWithOp);
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
1. Initialize a variable `maxSum` to the smallest possible integer value.
2. Use a nested loop to define the start (`i`) and end (`j`) of every possible subarray.
3. For each subarray `nums[i...j]`, calculate its sum, let's call it `currentSum`.
4. Update `maxSum = max(maxSum, currentSum)`. This handles the case with no operation.
5. Iterate through each element `k` from `i` to `j` in the current subarray.
6. For each element `nums[k]`, calculate the sum if it were squared: `sumWithOp = currentSum - nums[k] + nums[k] * nums[k]`.
7. Update `maxSum = max(maxSum, sumWithOp)`.
8. After checking all subarrays and all possible single-element squaring operations, `maxSum` will hold the result.

## Dynamic Programming
A more efficient approach uses dynamic programming. We can define the state at each index `i` by considering two possibilities for a subarray ending at `i`: either no operation has been performed, or one operation has been performed. By building up the solution based on these two states, we can solve the problem in a single pass.
**Time:** O(N), as we iterate through the array once to compute the DP values. · **Space:** O(N), for the two DP arrays used to store the states for each element.
**Pros:** Significantly more efficient with a linear time complexity.; Guaranteed to pass within time limits for typical constraints.
**Cons:** Uses extra space proportional to the input size, which can be a concern for very large inputs.
### Explanation
We define two DP states for each index `i`:

- `dp0[i]`: The maximum sum of a contiguous subarray ending at index `i` with **no** element squared. This is the standard Kadane's algorithm recurrence: `dp0[i] = max(nums[i], dp0[i-1] + nums[i])`.

- `dp1[i]`: The maximum sum of a contiguous subarray ending at index `i` with **one** element squared. This can happen in two ways:
    1. The squared element is `nums[i]`. The subarray before it must not have a squared element. The sum is `max(dp0[i-1], 0) + nums[i] * nums[i]`. We use `max(dp0[i-1], 0)` because if the best preceding subarray sum is negative, we are better off starting a new subarray from the current element.
    2. The squared element appeared before `nums[i]`. We simply extend the best subarray ending at `i-1` that already has a squared element: `dp1[i-1] + nums[i]`.

We take the maximum of these two possibilities for `dp1[i]`. The overall answer is the maximum value encountered in `dp0` or `dp1` at any index.

```java
class Solution {
    public int maxSumAfterOperation(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] dp0 = new int[n]; // max sum ending at i, no op
        int[] dp1 = new int[n]; // max sum ending at i, one op
        
        dp0[0] = nums[0];
        dp1[0] = nums[0] * nums[0];
        
        int maxSum = Math.max(dp0[0], dp1[0]);
        
        for (int i = 1; i < n; i++) {
            // State 0: No operation. Standard Kadane's.
            dp0[i] = Math.max(nums[i], dp0[i - 1] + nums[i]);
            
            // State 1: One operation.
            // Option A: The operation is on nums[i].
            int opOnCurrent = Math.max(0, dp0[i - 1]) + nums[i] * nums[i];
            // Option B: The operation was before nums[i].
            int opBeforeCurrent = dp1[i - 1] + nums[i];
            dp1[i] = Math.max(opOnCurrent, opBeforeCurrent);
            
            maxSum = Math.max(maxSum, Math.max(dp0[i], dp1[i]));
        }
        
        return maxSum;
    }
}
```
### Algorithm
1. Create two DP arrays, `dp0` and `dp1`, of size `n`.
2. `dp0[i]` will store the maximum subarray sum ending at index `i` with no operation.
3. `dp1[i]` will store the maximum subarray sum ending at index `i` with exactly one operation.
4. Initialize base cases for `i=0`: `dp0[0] = nums[0]` and `dp1[0] = nums[0] * nums[0]`.
5. Initialize `maxSum = max(dp0[0], dp1[0])`.
6. Iterate from `i = 1` to `n-1`:
   a. Calculate `dp0[i] = max(nums[i], dp0[i-1] + nums[i])`.
   b. Calculate `dp1[i] = max(dp1[i-1] + nums[i], max(dp0[i-1], 0) + nums[i] * nums[i])`.
   c. Update `maxSum = max(maxSum, dp0[i], dp1[i])`.
7. Return `maxSum`.

## Space-Optimized Dynamic Programming
This is the most optimal approach, improving upon the previous DP solution by reducing its space complexity. We notice that the DP calculation at index `i` only requires the results from index `i-1`. This dependency allows us to discard the DP arrays and use only a few variables to keep track of the necessary information from the previous step, achieving constant space complexity.
**Time:** O(N), because it involves a single pass through the input array. · **Space:** O(1), as we only use a few variables to store the running sums, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Highly efficient for all input sizes.
**Cons:** The logic can be slightly less intuitive to grasp initially compared to the O(N) space DP approach.
### Explanation
Instead of using full arrays `dp0` and `dp1`, we can use two variables to represent the state ending at the *current* element. Let's call them `noOpSum` and `oneOpSum`.

- `noOpSum`: Represents the max subarray sum ending at the current index with no operation.
- `oneOpSum`: Represents the max subarray sum ending at the current index with one operation.

As we iterate through the array, we update these two variables. The key is that the update for the current step `i` only depends on the values of `noOpSum` and `oneOpSum` from step `i-1`. We must be careful to use the `noOpSum` from the previous step when calculating the new `oneOpSum`.

```java
class Solution {
    public int maxSumAfterOperation(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        
        // max sum ending at current index, with no operation
        int noOpSum = nums[0]; 
        // max sum ending at current index, with one operation
        int oneOpSum = nums[0] * nums[0]; 
        
        int maxSum = Math.max(noOpSum, oneOpSum);
        
        for (int i = 1; i < n; i++) {
            // The new oneOpSum depends on the old noOpSum.
            // We must calculate the new oneOpSum before updating noOpSum.
            // Let's use a temporary variable for clarity.
            int prevNoOpSum = noOpSum;

            // Update oneOpSum for current index i:
            // Option A: Extend previous oneOpSum subarray.
            // Option B: Square current element and add to previous noOpSum subarray.
            oneOpSum = Math.max(oneOpSum + nums[i], (prevNoOpSum > 0 ? prevNoOpSum : 0) + nums[i] * nums[i]);
            
            // Update noOpSum for current index i (standard Kadane's):
            noOpSum = Math.max(nums[i], noOpSum + nums[i]);
            
            // Update the overall maximum sum found so far.
            maxSum = Math.max(maxSum, Math.max(noOpSum, oneOpSum));
        }
        
        return maxSum;
    }
}
```
### Algorithm
1. Initialize `noOpSum = nums[0]` and `oneOpSum = nums[0] * nums[0]`.
2. Initialize `maxSum = max(noOpSum, oneOpSum)`.
3. Iterate from `i = 1` to `n-1`:
   a. Store the `noOpSum` from the previous step in a temporary variable, say `prevNoOpSum`.
   b. Update `oneOpSum` for the current step: `oneOpSum = max(oneOpSum + nums[i], max(prevNoOpSum, 0) + nums[i] * nums[i])`.
   c. Update `noOpSum` for the current step: `noOpSum = max(nums[i], noOpSum + nums[i])`.
   d. Update the overall `maxSum = max(maxSum, noOpSum, oneOpSum)`.
4. Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int maxSumAfterOperation(int[] nums) {
    int length = nums.length;
    int[][] dp = new int[length][3];
    dp[0][0] = nums[0];
    dp[0][1] = nums[0] * nums[0];
    dp[0][2] = Integer.MIN_VALUE;
    int max = dp[0][1];
    for (int i = 1; i < length; i++) {
      dp[i][0] = Math.max(dp[i - 1][0], 0) + nums[i];
      dp[i][1] = Math.max(dp[i - 1][0], 0) + nums[i] * nums[i];
      dp[i][2] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][2]), 0) + nums[i];
      int curMax = Math.max(dp[i][1], dp[i][2]);
      max = Math.max(max, curMax);
    }
    return max;
  }
} class Solution {
public
  int maxSumAfterOperation(int[] nums) {
    int f = 0, g = 0;
    int ans = Integer.MIN_VALUE;
    for (int x : nums) {
      int ff = Math.max(f, 0) + x;
      int gg = Math.max(Math.max(f, 0) + x * x, g + x);
      f = ff;
      g = gg;
      ans = Math.max(ans, Math.max(f, g));
    }
    return ans;
  }
}
```

### Python

```python
from typing import List class Solution : def maximumSum ( self , nums : List [ int ]) -> int : dp = [] dp = [[ 0 ] * 3 for i in range ( len ( nums ))] dp [ 0 ][ 0 ] = nums [ 0 ] dp [ 0 ][ 1 ] = nums [ 0 ] * nums [ 0 ] dp [ 0 ][ 2 ] = float ( '-inf' ) result = float ( '-inf' ) for i in range ( 1 , len ( nums )): dp [ i ][ 0 ] = nums [ i ] + max ( 0 , dp [ i - 1 ][ 0 ]) dp [ i ][ 1 ] = nums [ i ] * nums [ i ] + max ( 0 , dp [ i - 1 ][ 0 ]) dp [ i ][ 2 ] = nums [ i ] + max ( 0 , dp [ i - 1 ][ 1 ], dp [ i - 1 ][ 2 ]) result = max ( result , dp [ i ][ 0 ], dp [ i ][ 1 ], dp [ i ][ 2 ]) return result if __name__ == "__main__" : print ( Solution (). maximumSum ([ 2 , - 1 , - 4 , - 3 ])) ########### class Solution : def maxSumAfterOperation ( self , nums : List [ int ]) -> int : f = g = 0 ans = - inf for x in nums : ff = max ( f , 0 ) + x gg = max ( max ( f , 0 ) + x * x , g + x ) f , g = ff , gg ans = max ( ans , f , g ) return ans
```

### CPP

```cpp
class Solution { public: int maxSumAfterOperation ( vector < int >& nums ) { int f = 0 , g = 0 ; int ans = INT_MIN ; for ( int x : nums ) { int ff = max ( f , 0 ) + x ; int gg = max ( max ( f , 0 ) + x * x , g + x ); f = ff ; g = gg ; ans = max ({ ans , f , g }); } return ans ; } };
```