Maximum Subarray Sum After One Operation - Solution & Explanation

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.