LeetCode 1746 - Maximum Subarray Sum After One Operation
The problem gives us an integer array nums, and we must perform exactly one operation on the array. The operation allows us to choose a single index i and replace the value nums[i] with its square, nums[i] nums[i].
Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming
Solution
Problem Understanding
The problem gives us an integer array nums, and we must perform exactly one operation on the array. The operation allows us to choose a single index i and replace the value nums[i] with its square, nums[i] * nums[i].
After performing this one required operation, we must compute the maximum possible sum of any non-empty contiguous subarray.
A subarray is a continuous segment of the array. We are free to choose any subarray after the operation is applied, but we must use the modified array that results from squaring exactly one element.
The important detail is that the operation is mandatory. We cannot skip it, even if squaring a number would appear harmful. Fortunately, squaring any integer produces a non-negative value, so the operation often improves the result, especially when applied to large negative numbers.
The constraints are important:
- The array length can be as large as
10^5 - Each value can range from
-10^4to10^4
These constraints immediately rule out expensive quadratic or cubic solutions. Any approach that examines all possible subarrays after all possible operations would be far too slow. Since n can be 100000, we should aim for a linear time dynamic programming solution.
Several edge cases are especially important:
- Arrays with a single element
- Arrays containing all negative numbers
- Arrays containing zeros
- Cases where squaring a positive number is better than squaring a negative number
- Cases where the optimal subarray contains only the squared element
- Cases where the optimal subarray extends across both positive and negative values
A naive implementation can easily make mistakes by either:
- Forgetting that the operation is mandatory
- Losing track of whether the operation has already been used
- Incorrectly handling transitions between subarrays
This naturally suggests a dynamic programming formulation with state tracking.
Approaches
Brute Force Approach
The most direct solution is to try every possible index as the squared element.
For each index i:
- Create a modified version of the array where
nums[i]becomesnums[i]^2 - Run Kadane's algorithm to compute the maximum subarray sum of the modified array
- Keep the best answer across all choices
This approach is correct because it explicitly evaluates every possible valid operation and computes the best subarray afterward.
However, the complexity is too high. There are n choices for the operation index, and each Kadane pass takes O(n) time. This produces an O(n^2) solution.
With n = 10^5, this would require around 10^10 operations in the worst case, which is far too slow.
Optimal Dynamic Programming Approach
The key insight is that we do not need to explicitly rebuild the array for every possible operation position.
Instead, while scanning the array from left to right, we can maintain two dynamic programming states:
- The maximum subarray sum ending at the current position without having used the operation yet
- The maximum subarray sum ending at the current position after already using the operation
This works because every subarray ending at index i must come from:
- Extending a previous subarray
- Starting fresh at the current position
The operation can only be used once, so when updating the second state, we either:
- Extend a previous subarray that already used the operation
- Use the operation at the current element for the first time
This converts the problem into a single linear scan.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Try every index as the squared element, then run Kadane's algorithm |
| Optimal | O(n) | O(1) | Dynamic programming with two running states |
Algorithm Walkthrough
- Define two DP states.
Let:
no_operationrepresent the maximum subarray sum ending at the current index without using the squaring operationwith_operationrepresent the maximum subarray sum ending at the current index after already using the operation
These states allow us to track whether the operation has been consumed. 2. Initialize the states using the first element.
For the first element:
no_operation = nums[0]with_operation = nums[0] * nums[0]
Since the operation is mandatory, the second state starts with the squared value. 3. Iterate through the remaining elements.
For each value num:
First compute squared = num * num.
4. Update the with_operation state.
There are three possibilities:
- Extend a previous subarray that already used the operation:
with_operation + num
- Use the operation on the current element while extending a previous untouched subarray:
no_operation + squared
- Start a completely new subarray using only the squared current element:
squared
We take the maximum of these choices.
5. Update the no_operation state.
This follows standard Kadane's algorithm:
- Extend the previous subarray:
no_operation + num
- Start a new subarray at the current element:
num
Take the maximum. 6. Track the global answer.
At every index, update the result using the best with_operation value seen so far.
We only use with_operation because the problem requires exactly one operation.
7. Return the final answer.
Why it works
The algorithm maintains a precise invariant:
no_operationalways stores the maximum subarray sum ending at the current index without squaring any elementwith_operationalways stores the maximum subarray sum ending at the current index after squaring exactly one element
Every valid subarray ending at the current position must belong to one of these categories, and the transition equations consider all possible ways to build such subarrays. Since every index is processed once and every transition is optimal, the final result is guaranteed to be the maximum achievable subarray sum after exactly one operation.
Python Solution
from typing import List
class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
no_operation = nums[0]
with_operation = nums[0] * nums[0]
answer = with_operation
for num in nums[1:]:
squared = num * num
new_with_operation = max(
with_operation + num,
no_operation + squared,
squared
)
new_no_operation = max(
no_operation + num,
num
)
with_operation = new_with_operation
no_operation = new_no_operation
answer = max(answer, with_operation)
return answer
The implementation directly follows the dynamic programming formulation.
The variable no_operation tracks the best subarray ending at the current index without using the square operation. This behaves exactly like Kadane's algorithm.
The variable with_operation tracks the best subarray ending at the current index after using the operation exactly once.
For each number, we compute the squared value once and reuse it in transitions.
The transition for with_operation considers all legal possibilities:
- Continuing an already modified subarray
- Applying the operation at the current index
- Starting a brand new subarray with the squared value
The answer is updated using only with_operation because the problem requires the operation to be used exactly once.
The algorithm uses only constant extra memory and processes the array in a single pass.
Go Solution
func max(a, b int) int {
if a > b {
return a
}
return b
}
func maxSumAfterOperation(nums []int) int {
noOperation := nums[0]
withOperation := nums[0] * nums[0]
answer := withOperation
for i := 1; i < len(nums); i++ {
num := nums[i]
squared := num * num
newWithOperation := max(
max(withOperation+num, noOperation+squared),
squared,
)
newNoOperation := max(
noOperation+num,
num,
)
withOperation = newWithOperation
noOperation = newNoOperation
answer = max(answer, withOperation)
}
return answer
}
The Go implementation mirrors the Python solution closely.
Go does not provide a built in max function for integers, so we define a helper function manually.
Slices are used naturally for array traversal. Since the constraints are small enough that integer overflow is not a concern for Go's int type on standard LeetCode environments, no special overflow handling is necessary.
The solution uses constant extra memory and performs a single linear scan.
Worked Examples
Example 1
Input:
nums = [2, -1, -4, -3]
Initial state:
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 0 | 2 | 2 | 4 | 4 |
Process index 1:
num = -1squared = 1
Compute:
new_with_operation = max(4 + (-1), 2 + 1, 1) = 3new_no_operation = max(2 + (-1), -1) = 1
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 1 | -1 | 1 | 3 | 4 |
Process index 2:
num = -4squared = 16
Compute:
new_with_operation = max(3 + (-4), 1 + 16, 16) = 17new_no_operation = max(1 + (-4), -4) = -3
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 2 | -4 | -3 | 17 | 17 |
Process index 3:
num = -3squared = 9
Compute:
new_with_operation = max(17 + (-3), -3 + 9, 9) = 14new_no_operation = max(-3 + (-3), -3) = -3
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 3 | -3 | -3 | 14 | 17 |
Final answer:
17
Example 2
Input:
nums = [1, -1, 1, 1, -1, -1, 1]
Initial state:
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
Process index 1:
num = -1squared = 1
Compute:
new_with_operation = max(1 - 1, 1 + 1, 1) = 2new_no_operation = max(1 - 1, -1) = 0
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 1 | -1 | 0 | 2 | 2 |
Process index 2:
num = 1squared = 1
Compute:
new_with_operation = max(2 + 1, 0 + 1, 1) = 3new_no_operation = max(0 + 1, 1) = 1
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 2 | 1 | 1 | 3 | 3 |
Process index 3:
num = 1squared = 1
Compute:
new_with_operation = max(3 + 1, 1 + 1, 1) = 4new_no_operation = max(1 + 1, 1) = 2
| Index | num | no_operation | with_operation | answer |
|---|---|---|---|---|
| 3 | 1 | 2 | 4 | 4 |
Remaining elements never improve the answer, so the final result is:
4
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each array element is processed exactly once |
| Space | O(1) | Only a few scalar variables are maintained |
The algorithm performs a constant amount of work per element. No nested loops or auxiliary data structures proportional to input size are used. The dynamic programming states are compressed into simple variables, which keeps the memory usage constant.
Test Cases
from typing import List
class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
no_operation = nums[0]
with_operation = nums[0] * nums[0]
answer = with_operation
for num in nums[1:]:
squared = num * num
new_with_operation = max(
with_operation + num,
no_operation + squared,
squared
)
new_no_operation = max(
no_operation + num,
num
)
with_operation = new_with_operation
no_operation = new_no_operation
answer = max(answer, with_operation)
return answer
solution = Solution()
assert solution.maxSumAfterOperation([2, -1, -4, -3]) == 17 # Provided example 1
assert solution.maxSumAfterOperation([1, -1, 1, 1, -1, -1, 1]) == 4 # Provided example 2
assert solution.maxSumAfterOperation([5]) == 25 # Single positive element
assert solution.maxSumAfterOperation([-5]) == 25 # Single negative element
assert solution.maxSumAfterOperation([0]) == 0 # Single zero
assert solution.maxSumAfterOperation([-1, -2, -3]) == 9 # Best to square largest magnitude negative
assert solution.maxSumAfterOperation([1, 2, 3]) == 12 # Square largest positive
assert solution.maxSumAfterOperation([1, -10, 2, 3]) == 106 # Large negative becomes huge positive
assert solution.maxSumAfterOperation([0, 0, 0]) == 0 # All zeros
assert solution.maxSumAfterOperation([-2, 5, -1]) == 9 # Square positive in middle
assert solution.maxSumAfterOperation([3, -2, 4]) == 17 # Square positive 4
assert solution.maxSumAfterOperation([-4, -1, -2]) == 16 # Best subarray may contain only squared element
assert solution.maxSumAfterOperation([1, -1, -1, 1]) == 2 # Multiple equivalent choices
| Test | Why |
|---|---|
[2, -1, -4, -3] |
Validates provided example with large negative squaring |
[1, -1, 1, 1, -1, -1, 1] |
Validates provided example with balanced positives and negatives |
[5] |
Single element positive array |
[-5] |
Single element negative array |
[0] |
Single zero edge case |
[-1, -2, -3] |
All negative values |
[1, 2, 3] |
All positive values |
[1, -10, 2, 3] |
Large negative transformed into dominant positive |
[0, 0, 0] |
All zeros |
[-2, 5, -1] |
Best operation applied to positive value |
[3, -2, 4] |
Operation on later positive value |
[-4, -1, -2] |
Optimal subarray is a single squared element |
[1, -1, -1, 1] |
Multiple optimal operation placements |
Edge Cases
One important edge case is a single element array. Since the operation is mandatory, the only possible result is the square of that element. A buggy implementation might accidentally return the original value instead. The initialization step correctly handles this by setting with_operation to nums[0] * nums[0] immediately.
Another important edge case is an array containing only negative values. Standard maximum subarray problems often return the least negative number, but here squaring a large magnitude negative number can create a large positive result. The algorithm correctly considers starting a new subarray with only the squared element through the transition:
with_operation = max(..., squared).
A third critical edge case occurs when the best subarray should restart after several harmful elements. If we always extend previous subarrays blindly, we can carry unnecessary negative sums forward. The Kadane style transitions avoid this issue by comparing extension versus starting fresh at every index.
A fourth subtle edge case occurs when squaring a positive number is better than squaring a negative one. It is tempting to assume the operation should always target a negative number, but squaring a sufficiently large positive can produce an even larger gain. Since the algorithm evaluates all possibilities dynamically, it naturally discovers the optimal operation position regardless of sign.