Maximum Sum Circular Subarray: Kadane's Algorithm Extended

You are given a circular integer array nums. Find the subarray with the maximum possible sum. Because the array is circular, the subarray is allowed to wrap around from the end back to the beginning.

This is LeetCode 918: Maximum Sum Circular Subarray, and it builds directly on top of Maximum Subarray. If you already know Kadane's algorithm, the question becomes: how do you handle wrapping? The trick is elegant, and once you see it, you will never forget it.

The two cases

When the array is circular, the maximum subarray falls into one of two cases:

1. Non-wrapping: the maximum subarray sits entirely within the linear array, just like a normal Kadane's problem.
2. Wrapping: the maximum subarray wraps around the end, including some suffix and some prefix of the array.

For case 1, you run standard Kadane's and get max_sum. But how do you efficiently find the best wrapping subarray?

The key insight: wrapping = total minus the minimum

Here is the trick. If a wrapping subarray uses elements from both ends but skips some middle portion, then the elements it skips form a contiguous non-wrapping subarray. The sum of the wrapping subarray is:

wrapping_sum = total_sum - sum_of_skipped_elements

To maximize wrapping_sum, you want to minimize the skipped portion. In other words, you want the minimum subarray sum. So:

wrapping_sum = total_sum - min_subarray_sum

You can find the minimum subarray sum with an inverted Kadane's algorithm in the same pass.

Walking through it step by step

Let's trace through nums = [5, -3, 5]. We compute max subarray, min subarray, and total sum, then combine them.

The wrapping subarray [5, 5] (index 2 then index 0) beats the non-wrapping max of 5. The answer is 10.

The code

Here is the full implementation in Python:

def maxSubarraySumCircular(self, nums: list[int]) -> int:
    max_sum = nums[0]
    min_sum = nums[0]
    cur_max = 0
    cur_min = 0
    total = 0
    for n in nums:
        cur_max = max(cur_max + n, n)
        max_sum = max(max_sum, cur_max)
        cur_min = min(cur_min + n, n)
        min_sum = min(min_sum, cur_min)
        total += n
    if max_sum < 0:
        return max_sum
    return max(max_sum, total - min_sum)

Let's walk through each piece:

1. cur_max and max_sum track the standard Kadane's maximum subarray. At each element, decide whether to extend the current subarray or restart.
2. cur_min and min_sum do the same thing but in reverse, finding the minimum subarray sum.
3. total accumulates the sum of all elements.
4. The edge case check: if max_sum is negative, every element is negative. In that case total - min_sum would be 0 (the "wrapping subarray" would be empty, which is not allowed). So you return max_sum directly, which is the largest single element.
5. Otherwise, the answer is the better of the non-wrapping max and the wrapping sum.

Why it works in one pass

Notice that we compute max_sum, min_sum, and total in a single loop. There is no need for multiple passes. Kadane's algorithm for the max and Kadane's algorithm for the min operate independently, and you can interleave them without any issues. Each variable only depends on the current element and the previous value of that same variable.

This gives us the same beautiful O(n) single-pass structure that makes Kadane's algorithm so practical.

Complexity analysis

Time: O(n). One pass through the array. Each element requires O(1) work: a few comparisons, additions, and max/min operations.

Space: O(1). Five variables regardless of input size. No extra arrays or data structures.

The building blocks

This problem is built on three reusable patterns:

1. Kadane's algorithm (extend or restart). The same decision pattern from Maximum Subarray. At each element, either extend the current subarray or start fresh. This gives you the non-wrapping max in O(n).

2. Min/max dual tracking. Similar to Maximum Product Subarray, you track two parallel values in the same pass. There you tracked max and min products because negatives flip signs. Here you track max and min sums because the min subarray gives you the wrapping case for free.

3. Complement thinking. Instead of directly computing the wrapping subarray (which would require trying all split points), you compute its complement: the minimum contiguous subarray in the middle. The wrapping sum is total - min. This "find what you skip instead of what you keep" technique appears in many problems involving circular or wrap-around constraints.

Edge cases to watch for

• All negative like [-3, -5, -1]: answer is -1 (the largest element). The max_sum check catches this.
• All positive like [1, 2, 3]: the entire array is optimal. min_sum would be the smallest element. total - min_sum equals the sum of the other elements, which might be less than total. Standard Kadane's returns total here, so the non-wrapping case wins.
• Single element [5] or [-3]: max_sum = min_sum = total = that element. Works correctly.
• Wrapping is optimal like [5, -3, 5]: total - min_sum = 7 - (-3) = 10 beats max_sum = 5.
• Non-wrapping is optimal like [1, -2, 3, -2]: max_sum = 3, total - min_sum = 0 - (-2) = 2. Non-wrapping wins.

From understanding to recall

You now understand the complement trick: the maximum wrapping subarray equals the total minus the minimum non-wrapping subarray. The logic is clean and the code is short. But will you remember the edge case check for all-negative arrays during an interview? Will you remember to run both max and min Kadane's in the same loop?

Spaced repetition bridges this gap. You revisit the dual-Kadane's pattern at increasing intervals, writing the solution from scratch each time. After a few reps, the complement insight and the edge case handling become automatic.

The complement thinking pattern and Kadane's extend-or-restart decision are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding problems randomly and hoping things stick.

Related posts

• Maximum Subarray - The foundation: standard Kadane's algorithm for finding the maximum sum contiguous subarray
• Maximum Product Subarray - Another Kadane variant that tracks both max and min running values
• House Robber - Circular constraint variant where you cannot use adjacent elements