Skip to main content
Talentd

Maximum Subarray Sum After One Operation - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming5 min readAsked at: Sprinklr
Practice this problem

Problem Statement

You are given an integer array nums. You must perform exactly one operation where you can replace one element nums[i] with nums[i] * nums[i]. 

Return the maximum possible subarray sum after exactly one operation. The subarray must be non-empty.

 

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.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array. You may choose exactly one element and square it (x → x²). After performing this operation, find the maximum possible sum of a contiguous subarray. The operation can significantly increase a value, so the optimal subarray may include the squared element or even start at it.

Approach 1: Brute Force with Modified Subarray Enumeration (O(n²) time, O(1) space)

Try every index as the element where the operation is applied. For each candidate index i, treat nums[i] as squared and compute the maximum subarray sum using a standard scan. This can be done by recalculating subarray sums around the modified array or running a variant of Kadane’s algorithm after applying the change. Since the operation position can be any of the n indices and each evaluation requires a full pass, the complexity becomes O(n²). This approach helps reason about how the squared element affects the surrounding subarray but does not scale well for large inputs.

Approach 2: Dynamic Programming with Two States (Kadane Variant) (O(n) time, O(1) space)

The optimal solution extends Kadane’s algorithm from Array problems with an additional state representing whether the operation has already been used. Track two running values while iterating through the array:

noOp — maximum subarray sum ending at the current index with no operation used yet.
withOp — maximum subarray sum ending at the current index where one element has already been squared.

For each number x, update the states:

noOp = max(x, noOp + x)

withOp = max(x*x, noOp_prev + x*x, withOp + x)

This transition captures all possibilities: starting a new subarray using the squared value, extending a previous subarray and applying the square at the current index, or extending a subarray where the operation was already used earlier. The answer is the maximum value seen in withOp. The algorithm processes each element once and stores only two variables, giving O(n) time and O(1) space.

This pattern is common in Dynamic Programming problems where you track states representing whether a special action has been used. Conceptually, it’s a modified Kadane’s algorithm applied to the array while maintaining two parallel subarray states.

Recommended for interviews: The dynamic programming approach with two states is the expected solution. Mentioning the brute-force idea shows you understand the effect of squaring different elements, but the O(n) Kadane-style DP demonstrates algorithmic optimization and strong familiarity with dynamic programming patterns used in array subarray problems.

Solution

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n²)O(1)Useful for understanding the effect of squaring each index and validating logic during early problem exploration.
Dynamic Programming (Kadane Variant)O(n)O(1)Optimal solution for interviews and production. Handles large arrays efficiently with constant memory.

Video Solution

1746. Maximum Subarray Sum After One Operation - Week 5/5 Leetcode December Challenge • Programming Live with Larry • 392 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximum Subarray Sum After One Operation easy or hard?
The problem is classified as Medium. It requires recognizing that the square operation creates two dynamic states and adapting Kadane’s algorithm accordingly. Once the DP transition is identified, the implementation becomes straightforward.
Maximum Subarray Sum After One Operation Python/Java solution
Implement a Kadane-style dynamic programming loop that tracks two values: the best subarray sum without using the operation and the best sum after using it. The same logic works across Python, Java, C++, Go, and Rust with O(n) time and constant space.
How to solve Maximum Subarray Sum After One Operation in O(n)?
Maintain two running values while iterating through the array: one for subarrays that have not used the operation and another for those that already squared an element. Update them using Kadane-style transitions that consider extending the subarray or applying the square at the current index. Track the maximum value seen in the state where the operation has been used.
What is the best approach for Maximum Subarray Sum After One Operation?
The best approach uses dynamic programming with two states, extending Kadane’s algorithm. Track the maximum subarray ending at each index with and without using the square operation. This method processes the array once, giving O(n) time complexity and O(1) space.
Is Maximum Subarray Sum After One Operation asked at Google/Amazon/Meta?
This problem represents a classic dynamic programming variation of the maximum subarray problem. Similar patterns frequently appear in interviews at companies like Amazon, Google, and Meta where candidates must modify Kadane’s algorithm to handle an additional constraint or operation.
What data structure is used in Maximum Subarray Sum After One Operation?
The solution primarily uses dynamic programming with constant variables rather than complex data structures. The array is processed sequentially while maintaining two DP states representing whether the square operation has been applied.
What is the time complexity of Maximum Subarray Sum After One Operation?
The optimal solution runs in O(n) time because each element is processed exactly once while updating two DP states. Only constant extra memory is required, so the space complexity is O(1).

Ready to solve this problem?

Practice Maximum Subarray Sum After One Operation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Subarray