Solution Explanation

This problem asks to find the maximum subarray sum after performing exactly one operation: squaring one element in the input array nums. A dynamic programming approach efficiently solves this.

Approach:

We use two variables, f and g, to track the maximum subarray sums at each step.

• f: Represents the maximum subarray sum ending at the current index without squaring any element.
• g: Represents the maximum subarray sum ending at the current index after squaring at least one element.

The algorithm iterates through the array. For each element x:

1. Update f: The maximum subarray sum ending at the current index without squaring is either the current element itself (x) or the continuation of the previous maximum sum (f), if positive. If f is negative, it's better to start a new subarray from x.

2. Update g: The maximum subarray sum ending at the current index after squaring is the maximum of two possibilities:

   • Continuing the previous maximum subarray sum with a squared element (g + x): This means the squaring operation happened before the current element.
   • Starting a new subarray with a squared element (max(f, 0) + x*x): This means we are squaring the current element.

3. Update the overall maximum ans: After updating f and g, we update ans to be the maximum of the current ans, f, and g.

Time Complexity: O(N), where N is the length of the array. We iterate through the array once.

Space Complexity: O(1). We only use a constant number of variables.

Code Explanation (Python):

class Solution:
    def maxSumAfterOperation(self, nums: List[int]) -> int:
        f = g = 0  # Initialize f and g
        ans = -inf  # Initialize the maximum sum to negative infinity
 
        for x in nums:
            ff = max(f, 0) + x  # Update f
            gg = max(max(f, 0) + x * x, g + x)  # Update g
            f, g = ff, gg  # Assign updated values
            ans = max(ans, f, g)  # Update the overall maximum
 
        return ans
 

The code in other languages (Java, C++, Go, Rust) follows the same logic with minor syntax differences. They all implement the dynamic programming approach described above, achieving linear time complexity.