Maximum Subarray Sum with One Square Allowed – Complete C# Explanation

1. Problem Understanding

We are given an integer array. We need to find the maximum sum of a contiguous subarray, where we are allowed to square at most one element in that subarray.

Squaring an element means multiplying it by itself.

For example:

Input:  [-1, -2, 3, -2, 3]
Output: 10

Let's understand why the answer is 10.

Choose this subarray:

[3, -2, 3]

Square the element -2:

3 + (-2 * -2) + 3
= 3 + 4 + 3
= 10

Therefore, the maximum subarray sum is 10.

Important conditions:

• The subarray must be contiguous.
• We can square zero or one element.
• We cannot square more than one element.
• We need to find the maximum possible sum.

2. Understanding the Concept

Before writing the code, let's understand the main algorithm.

The problem is related to Kadane's Algorithm.

What is Kadane's Algorithm?

Kadane's Algorithm is used to find the maximum sum of a contiguous subarray.

For example:

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The maximum subarray is:

[4, -1, 2, 1]

Sum:

4 + (-1) + 2 + 1 = 6

Kadane's Algorithm maintains the maximum subarray sum ending at the current position.

The logic is:

currentSum = Math.Max(arr[i], currentSum + arr[i]);

There are two possibilities:

1. Start a new subarray from the current element.
2. Extend the previous subarray by adding the current element.

But our problem has an additional condition: we can square one element.

So, normal Kadane's Algorithm alone is not enough. We need to maintain two different states.

3. Dynamic Programming Approach

We maintain two important variables.

State 1: noSquare

It stores the maximum subarray sum ending at the current index without squaring any element.

State 2: withSquare

It stores the maximum subarray sum ending at the current index after squaring exactly one element.

We also maintain:

State 3: ans

It stores the overall maximum sum found so far.

Why do we need two states?

Consider:

arr = [3, -2, 3]

Without squaring:

3 + (-2) + 3 = 4

With squaring:

3 + 4 + 3 = 10

We need to remember both possibilities because the best decision at the current element depends on what happened previously.

4. Understanding the Formula

Let's understand each formula.

Formula 1: Without Squaring

noSquare = Math.Max(x, noSquare + x);

Here, x represents the current array element.

We have two choices:

• Start a new subarray using the current element.
• Continue the previous subarray.

Mathematically:

\[ noSquare = \max(x,\ previousNoSquare+x) \]

Formula 2: With Squaring

When we square the current element, we have three possibilities:

Option 1: Start a new subarray with the squared element.

x * x

Example:

arr[i] = -2

(-2) * (-2) = 4

Option 2: Extend the previous subarray without squaring and square the current element.

previousNoSquare + (x * x)

Example:

Previous subarray sum = 3
Current element = -2

3 + (-2 * -2) = 7

Option 3: Continue the previous subarray where one element was already squared.

previousWithSquare + x

Example:

Previous sum = 7
Current element = 3

7 + 3 = 10

Therefore, the formula becomes:

\[ \begin{aligned} withSquare = \max(&x^2,\\ &previousNoSquare+x^2,\\ &previousWithSquare+x) \end{aligned} \]

Important: We must use the previous noSquare value before updating it. Otherwise, the calculation will be incorrect.

5. Complete C# Code

class Solution {
    public int maximumSubarray(int[] arr) {

        int n = arr.Length;

        // Maximum sum without squaring
        int noSquare = arr[0];

        // Maximum sum with exactly one squared element
        int withSquare = arr[0] * arr[0];

        // Store the overall maximum
        int ans = Math.Max(noSquare, withSquare);

        for (int i = 1; i < n; i++) {

            int x = arr[i];

            // Store the previous value
            int previousNoSquare = noSquare;

            // Case 1: Without squaring
            noSquare = Math.Max(x, noSquare + x);

            // Case 2: With exactly one square
            withSquare = Math.Max(
                Math.Max(x * x, previousNoSquare + x * x),
                withSquare + x
            );

            // Update the maximum answer
            ans = Math.Max(ans,
                Math.Max(noSquare, withSquare));
        }

        return ans;
    }
}

6. Code Explanation – Line by Line

Step 1: Get array length