Problem Description

You have an integer array nums and need to perform exactly one operation on it. The operation allows you to select any element nums[i] and replace it with its square value nums[i] * nums[i].

After performing this single operation, you need to find the maximum possible sum of any contiguous subarray. The subarray must contain at least one element (non-empty).

For example, if you have an array [2, -1, 3], you could:

• Square the first element to get [4, -1, 3], then the maximum subarray sum would be 4 + (-1) + 3 = 6
• Square the second element to get [2, 1, 3], then the maximum subarray sum would be 2 + 1 + 3 = 6
• Square the third element to get [2, -1, 9], then the maximum subarray sum would be 9

The goal is to strategically choose which element to square such that the resulting maximum subarray sum is as large as possible, then return that maximum sum.

The solution uses dynamic programming with two states:

• f: tracks the maximum subarray sum ending at the current position without using the square operation
• g: tracks the maximum subarray sum ending at the current position with the square operation already used

At each position, we update both states and keep track of the overall maximum seen so far.

Intuition

The key insight is that this problem is a variation of the classic maximum subarray sum problem (Kadane's algorithm), but with a twist - we must use the squaring operation exactly once.

When thinking about any subarray, we have two scenarios to consider:

1. The squaring operation hasn't been used yet in this subarray
2. The squaring operation has already been used somewhere in this subarray

This naturally leads us to track two different states as we iterate through the array. At each position, we need to know:

• What's the best subarray sum ending here if we haven't used the square operation?
• What's the best subarray sum ending here if we've already used the square operation?

For any element at position i, we have choices:

• If we haven't squared anything yet (f state), we can either:

  • Continue the previous subarray or start fresh (classic Kadane's logic): max(f, 0) + x

• If we want to have used the square operation by position i (g state), we can either:

  • Square the current element and combine with the best non-squared subarray ending before it: max(f, 0) + x * x
  • Or we already squared something earlier and just add the current element: g + x

The beauty of this approach is that it handles all cases: squaring negative numbers (which become positive), squaring positive numbers (which become larger), and choosing the optimal position to apply the operation. By maintaining these two states and taking their maximum at each step, we ensure we find the globally optimal solution.

The initialization with f = g = 0 works because we can always choose to start a new subarray at any position, and the constraint that we must use the operation exactly once is naturally enforced by our state transitions.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with two state variables to track the maximum subarray sum with and without using the squaring operation.

State Variables:

• f: Maximum subarray sum ending at the current position without using the square operation
• g: Maximum subarray sum ending at the current position with the square operation already used
• ans: Global maximum found so far (initialized to negative infinity to handle all negative arrays)

Algorithm Steps:

1. Initialize states: Start with f = g = 0 and ans = -inf

2. Iterate through each element x in nums:

   a. Update f (no square used):

   ff = max(f, 0) + x

   This follows Kadane's algorithm - either extend the previous subarray or start fresh if the previous sum was negative.

   b. Update g (square operation used):

   gg = max(max(f, 0) + x * x, g + x)

   We take the maximum of two options:

   • Square the current element: max(f, 0) + x * x (use the best non-squared subarray before this and square current element)
   • Already squared earlier: g + x (extend the subarray that already used the square operation)

   c. Update states and answer:

   f, g = ff, gg
   ans = max(ans, f, g)

   Store the new states and update the global maximum.

3. Return the result: After processing all elements, ans contains the maximum possible subarray sum with exactly one square operation.

Why this works:

• The algorithm ensures we consider all possible positions to apply the square operation
• By tracking both states simultaneously, we can make optimal decisions at each position
• The max(f, 0) pattern ensures we start fresh when continuing would decrease our sum
• The final answer considers both states at every position, capturing all possible optimal subarrays

Time Complexity: O(n) - single pass through the array Space Complexity: O(1) - only using constant extra space for state variables

Example Walkthrough

Let's walk through the algorithm with the array nums = [2, -3, 4].

Initial State:

• f = 0 (max subarray sum ending here, no square used)
• g = 0 (max subarray sum ending here, square used)
• ans = -inf (global maximum)

Step 1: Process element x = 2 (index 0)

• Calculate new f: ff = max(0, 0) + 2 = 2
  • We either start fresh or extend. Since f=0, we get 0+2=2
• Calculate new g: gg = max(max(0, 0) + 2*2, 0 + 2) = max(4, 2) = 4
  • Option 1: Square current element: 0 + 4 = 4
  • Option 2: Already squared earlier: 0 + 2 = 2
  • Choose maximum: 4
• Update states: f = 2, g = 4
• Update answer: ans = max(-inf, 2, 4) = 4

Step 2: Process element x = -3 (index 1)

• Calculate new f: ff = max(2, 0) + (-3) = 2 - 3 = -1
  • Extend previous subarray: 2 + (-3) = -1
• Calculate new g: gg = max(max(2, 0) + (-3)*(-3), 4 + (-3)) = max(11, 1) = 11
  • Option 1: Square current element: 2 + 9 = 11
  • Option 2: Already squared earlier: 4 + (-3) = 1
  • Choose maximum: 11
• Update states: f = -1, g = 11
• Update answer: ans = max(4, -1, 11) = 11

Step 3: Process element x = 4 (index 2)

• Calculate new f: ff = max(-1, 0) + 4 = 0 + 4 = 4
  • Start fresh since previous f=-1 is negative
• Calculate new g: gg = max(max(-1, 0) + 4*4, 11 + 4) = max(16, 15) = 16
  • Option 1: Square current element: 0 + 16 = 16
  • Option 2: Already squared earlier: 11 + 4 = 15
  • Choose maximum: 16
• Update states: f = 4, g = 16
• Update answer: ans = max(11, 4, 16) = 16

Result: The maximum possible subarray sum is 16.

This comes from the subarray [-3, 4] where we square the 4 to get [-3, 16], giving sum = -3 + 16 = 13. Wait, let me recalculate...

Actually, looking at step 3 more carefully:

• The g = 16 represents just taking element 4 and squaring it (starting fresh), which gives us 16.
• This is indeed the optimal solution: take the single element subarray [4] and square it to get [16].

The algorithm correctly identified that the best strategy is to take just the element 4 alone and square it, yielding a maximum sum of 16.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once, performing a constant amount of operations for each element (calculating ff, gg, updating variables, and finding maximum values).

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. The variables f, g, ff, gg, and ans are the only additional memory used, which doesn't scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle All-Negative Arrays

A common mistake is initializing the maximum result to 0, which fails when all array elements are negative.

Incorrect:

max_sum = 0  # Wrong! Fails for arrays like [-5, -2, -3]

Correct:

max_sum = float('-inf')  # Handles all-negative arrays correctly

2. Incorrectly Updating the with_square State

Many implementations forget that once the square operation is used, we cannot use it again. A common error is allowing multiple squares:

Incorrect:

# This allows squaring multiple elements
new_with_square = max(no_square + num * num, with_square + num * num)

Correct:

# Square current element OR extend already-squared subarray (no more squares)
new_with_square = max(max(no_square, 0) + num * num, with_square + num)

3. Not Considering Starting Fresh When Previous Sum is Negative

Failing to reset when the previous subarray sum becomes negative leads to suboptimal results:

Incorrect:

new_no_square = no_square + num  # Always extends, even if no_square < 0
new_with_square = no_square + num * num  # Same issue

Correct:

new_no_square = max(no_square, 0) + num
new_with_square = max(max(no_square, 0) + num * num, with_square + num)

4. Updating States Before Using Them

Modifying state variables before all calculations are complete causes incorrect transitions:

Incorrect:

for num in nums:
    no_square = max(no_square, 0) + num  # Modified immediately
    with_square = max(max(no_square, 0) + num * num, with_square + num)  # Uses modified no_square!

Correct:

for num in nums:
    new_no_square = max(no_square, 0) + num
    new_with_square = max(max(no_square, 0) + num * num, with_square + num)
    no_square = new_no_square  # Update after all calculations
    with_square = new_with_square

5. Only Checking Final States Instead of All Positions

The maximum subarray might end at any position, not just the last element:

Incorrect:

for num in nums:
    # ... update states ...
return max(no_square, with_square)  # Only checks final position

Correct:

for num in nums:
    # ... update states ...
    max_sum = max(max_sum, no_square, with_square)  # Check at every position
return max_sum