Maximum Subarray — Important Interview Variations

Prerequisite: Kadane’s Algorithm . maximum-subarray-sum

Core idea of Kadane:
best subarray ending at i
    =
max(nums[i], previous_best + nums[i])
The variations below are useful because each changes what state we need to remember or how we transform the problem.

1. Maximum Circular Subarray ⭐⭐⭐⭐⭐

Problem

The array is circular, meaning the last element is adjacent to the first.

Find the maximum-sum non-empty subarray.

Example:

nums = [5, -3, 5]

Normal maximum:
[5, -3, 5] = 7

Circular maximum:
[5] + [5] = 10

Answer = 10

Key Insight

A maximum circular subarray has only two possibilities:

Case 1 — It does NOT wrap

Just use normal Kadane.

[ ... maximum contiguous section ... ]

Case 2 — It DOES wrap

A wrapping subarray looks like:

[ suffix ][ prefix ]

Instead of finding that directly, find the minimum subarray in the middle and remove it.

Total array
     │
     ├──── minimum subarray ────┤
     │                          │
     └── remaining elements ────┘
              ↑
       maximum wrapping sum

Therefore:

circular_max = total_sum - minimum_subarray_sum

Final answer:

max(normal_max, total_sum - min_subarray)

Important Edge Case

If all numbers are negative, then:

total_sum - min_subarray

would effectively select an empty subarray.

But the problem requires a non-empty subarray.

Example:

[-3, -2, -5]

Normal maximum:

-2

So if

max_sum < 0

return max_sum.

Complete Code

def maxSubarraySumCircular(nums):
    total = sum(nums)

    # Normal Kadane
    max_sum = nums[0]
    current_max = nums[0]

    # Minimum Kadane
    min_sum = nums[0]
    current_min = nums[0]

    for x in nums[1:]:
        current_max = max(x, current_max + x)
        max_sum = max(max_sum, current_max)

        current_min = min(x, current_min + x)
        min_sum = min(min_sum, current_min)

    # All elements are negative
    if max_sum < 0:
        return max_sum

    return max(max_sum, total - min_sum)

Complexity

Time: O(n)
Auxiliary Space: O(1)

Interview Insight

The beautiful trick is:

Maximum circular subarray = total sum − minimum subarray

But remember the all-negative edge case.

2. Maximum Product Subarray ⭐⭐⭐⭐⭐

Problem

Find the contiguous subarray having the maximum product.

Example:

nums = [2, 3, -2, 4]

Answer = 6

Subarray:
[2, 3]

Why Can’t We Simply Use Kadane?

For sums:

negative + something

has predictable behavior.

For products, a negative number can completely change the situation.

Example:

[-2, 3, -4]

The two negatives produce a positive product:

(-2) × 3 × (-4) = 24

So a very small negative product may become the largest positive product after multiplying by another negative.

Therefore, at every position we need to remember:

maximum product ending here
minimum product ending here

Why Minimum?

Suppose:

current_min = -10
current_max = 3
x = -5

Then:

current_min * x = 50
current_max * x = -15

The previous minimum becomes the new maximum.

State

Maintain:

max_prod = maximum product ending at current position

min_prod = minimum product ending at current position

For each x:

new_max = max(x,
              x * old_max,
              x * old_min)

new_min = min(x,
              x * old_max,
              x * old_min)

The answer is the maximum max_prod encountered.

Complete Code

def maxProduct(nums):
    current_max = nums[0]
    current_min = nums[0]
    answer = nums[0]

    for x in nums[1:]:

        old_max = current_max
        old_min = current_min

        current_max = max(
            x,
            x * old_max,
            x * old_min
        )

        current_min = min(
            x,
            x * old_max,
            x * old_min
        )

        answer = max(answer, current_max)

    return answer

Complexity

Time: O(n)
Auxiliary Space: O(1)

Interview Takeaway

For maximum product:

Track both maximum and minimum.

Because:

negative × negative = positive

This is one of the most important differences between Kadane for sum and Kadane-like DP for product.

3. Maximum Subarray Sum with One Deletion ⭐⭐⭐⭐

Problem

You may delete at most one element from the array.

Find the maximum possible subarray sum.

Example:

nums = [1, -2, 0, 3]

Without deletion:
1 + (-2) + 0 + 3 = 2

Delete -2:
1 + 0 + 3 = 4

Answer = 4

Key Insight

At every position, maintain two states:

`no_delete`

Maximum sum ending here with no deletion used.

`one_delete`

Maximum sum ending here with one deletion already used.

For current value x:

no_delete =
    max(x,
        no_delete + x)

For one_delete, we have two possibilities:

Don’t delete `x`

one_delete + x

Delete `x`

Then the previous subarray must have used no deletion:

previous_no_delete

Therefore:

one_delete =
    max(previous_one_delete + x,
        previous_no_delete)

Complete Code

def maximumSum(nums):
    no_delete = nums[0]
    one_delete = float("-inf")

    answer = nums[0]

    for x in nums[1:]:

        old_no_delete = no_delete
        old_one_delete = one_delete

        no_delete = max(
            x,
            old_no_delete + x
        )

        one_delete = max(
            old_one_delete + x,
            old_no_delete
        )

        answer = max(
            answer,
            no_delete,
            one_delete
        )

    return answer

Complexity

Time: O(n)
Auxiliary Space: O(1)

Why Does `one_delete = old_no_delete` Mean Delete `x`?

Suppose:

nums = [1, -2, 3]

At -2:

old_no_delete = 1

If we delete -2, the resulting subarray is simply:

[1]

So the new one_delete state is:

Then when 3 arrives:

1 + 3 = 4

giving:

[1, -2, 3]
      ↓
     delete
      ↓
[1, 3]

Interview Takeaway

This is a classic example of:

Adding one extra state to Kadane to represent one special operation.

This pattern generalizes to many DP problems.

4. Maximum Average Subarray ⭐⭐⭐⭐

Standard Interview Version

Given an array and integer k, find the maximum average of any contiguous subarray of exactly length k.

Example:

nums = [1,12,-5,-6,50,3]
k = 4

Best window:

[12,-5,-6,50]

sum = 51

average = 51 / 4 = 12.75

Important Observation

Because the length is fixed:

maximum average

is equivalent to:

maximum sum

You don’t need Kadane.

You need a sliding window.

Complete Code

def findMaxAverage(nums, k):
    window_sum = sum(nums[:k])
    best_sum = window_sum

    for right in range(k, len(nums)):
        window_sum += nums[right]
        window_sum -= nums[right - k]

        best_sum = max(best_sum, window_sum)

    return best_sum / k

Complexity

Time: O(n)
Auxiliary Space: O(1)

Why Not Divide Every Window by `k`?

Because k is constant.

If:

sum1 > sum2

then:

sum1/k > sum2/k

So simply maximize the sum.

Important Distinction

If the problem says:

Maximum average subarray of exactly k elements

→ Sliding Window

If it says:

Maximum average subarray with arbitrary length

that’s a different and substantially harder problem; don’t automatically apply this solution.

For standard interview preparation, the fixed-length version (LeetCode 643) is the important one.

5. Maximum Sum Rectangle in a 2D Matrix ⭐⭐⭐⭐⭐

maximum-sum-rectangle-in-a-2d-matrix-(kadane-2d)

Problem

Given a 2D matrix, find the rectangular submatrix having the maximum sum.

Example:

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

We want the rectangle with maximum sum.

Key Insight

This is essentially:

Kadane’s Algorithm + Row Compression

Suppose we choose:

top = row 1
bottom = row 2

Combine those rows column-by-column.

Row 1:   1   2  -1
Row 2:  -3   4   5

Combined:
        -2   6   4

Now the 2D rectangle problem becomes a 1D maximum subarray problem:

[-2, 6, 4]

Kadane finds:

6 + 4 = 10

which corresponds to a rectangle spanning those two rows.

Algorithm

Fix the top row.

Then progressively move the bottom row downward.

For every new bottom row:

Add that row into a column-sum array.
Run Kadane on the column sums.
Keep the best result.

Conceptually:

Choose top row
      ↓
Add next row
      ↓
Column sums
      ↓
Kadane
      ↓
Add next row
      ↓
Column sums
      ↓
Kadane
      ↓
...

Complete Code

def maxSumRectangle(matrix):

    rows = len(matrix)
    cols = len(matrix[0])

    answer = float("-inf")

    for top in range(rows):

        column_sum = [0] * cols

        for bottom in range(top, rows):

            # Compress rows top..bottom
            for col in range(cols):
                column_sum[col] += matrix[bottom][col]

            # Kadane on compressed array
            current = column_sum[0]
            best = column_sum[0]

            for col in range(1, cols):
                current = max(
                    column_sum[col],
                    current + column_sum[col]
                )

                best = max(best, current)

            answer = max(answer, best)

    return answer

Complexity

For an R × C matrix:

Choose top row: O(R)
Choose bottom row: O(R)
Update column sums: O(C)
Kadane: O(C)

Therefore:

Time = O(R² × C)

Auxiliary space:

O(C)

assuming we compress along the columns.

Why This Is Important

This is a very common example of a 2D problem being reduced to a known 1D problem.

The important thought process is:

2D rectangle
      ↓
Fix top and bottom boundaries
      ↓
Compress rows into 1D column sums
      ↓
Maximum subarray
      ↓
Kadane

You should recognize this pattern rather than memorize the implementation.

Overall Comparison

Problem	Main Technique	Time	Aux. Space
Maximum Subarray	Kadane	`O(n)`	`O(1)`
Maximum Circular Subarray	Kadane × 2	`O(n)`	`O(1)`
Maximum Product Subarray	Track min + max	`O(n)`	`O(1)`
Max Sum with One Deletion	2-state Kadane	`O(n)`	`O(1)`
Maximum Average, fixed `k`	Sliding Window	`O(n)`	`O(1)`
Maximum Sum Rectangle	Row compression + Kadane	`O(R²C)`	`O(C)`

How to Recognize the Variation

Maximum SUM
    ↓
Kadane

Circular array
    ↓
Normal Kadane
+
Minimum Kadane

PRODUCT
    ↓
Track MAX + MIN

One deletion allowed
    ↓
Kadane + extra state

Average of exactly k elements
    ↓
Fixed-size Sliding Window

2D maximum rectangle
    ↓
Compress rows
+
1D Kadane

High-ROI Interview Takeaways

⭐ Maximum Circular Subarray

Know the transformation:

max circular
=
max(normal max,
    total - minimum subarray)

Edge case: all elements negative.

⭐ Maximum Product Subarray

Remember:

max + min

because a negative can turn the minimum into the maximum.

⭐ Maximum Sum with One Deletion

Remember the two states:

no_delete
one_delete

This is a useful example of state augmentation.

⭐ Maximum Average Subarray

For exactly k elements:

maximum average
        ↓
maximum sum
        ↓
sliding window

Don’t unnecessarily use binary search or complicated DP.

⭐ Maximum Sum Rectangle

Remember:

2D
 ↓
Fix two boundaries
 ↓
Compress
 ↓
1D
 ↓
Kadane

This is the most important conceptual follow-up among the five because it demonstrates how a familiar 1D algorithm can be lifted to 2D.

What NOT to Over-study

For standard FAANG/product-company SWE preparation, I would not go down rabbit holes such as:

exotic maximum-subarray variants
divide-and-conquer implementations of Kadane
advanced max-average binary-search formulations unless specifically asked
higher-dimensional Kadane
specialized matrix algorithms

The five variations above are enough to build the practical “maximum subarray family” you are likely to encounter in interviews.

Maximum Subarray — Important Interview Variations

1. Maximum Circular Subarray ⭐⭐⭐⭐⭐

Problem

Key Insight

Case 1 — It does NOT wrap

Case 2 — It DOES wrap

Important Edge Case

Complete Code

Complexity

Interview Insight

2. Maximum Product Subarray ⭐⭐⭐⭐⭐

Problem

Why Can’t We Simply Use Kadane?

Why Minimum?

State

Complete Code

Complexity

Interview Takeaway

3. Maximum Subarray Sum with One Deletion ⭐⭐⭐⭐

Problem

Key Insight

no_delete

one_delete

Don’t delete x

Delete x

Complete Code

Complexity

Why Does one_delete = old_no_delete Mean Delete x?

Interview Takeaway

4. Maximum Average Subarray ⭐⭐⭐⭐

Standard Interview Version

Important Observation

Complete Code

Complexity

Why Not Divide Every Window by k?

Important Distinction

5. Maximum Sum Rectangle in a 2D Matrix ⭐⭐⭐⭐⭐

Problem

Key Insight

Algorithm

Complete Code

Complexity

Why This Is Important

Overall Comparison

How to Recognize the Variation

High-ROI Interview Takeaways

⭐ Maximum Circular Subarray

⭐ Maximum Product Subarray

⭐ Maximum Sum with One Deletion

⭐ Maximum Average Subarray

⭐ Maximum Sum Rectangle

What NOT to Over-study

Local Graph View

`no_delete`

`one_delete`

Don’t delete `x`

Delete `x`

Why Does `one_delete = old_no_delete` Mean Delete `x`?

Why Not Divide Every Window by `k`?