Maximum Subarray (Circular)

Interview Prep

StandardDynamic Programming Variation of Maximum Subarrayarraysdpkadane

The problem

Same as Maximum Subarray, but the array is circular — the last element connects to the first. The maximum subarray may wrap around the end. Return the largest sum. Non-empty subarrays only.

Pattern: complement trick

The clean approach uses a beautiful observation: any non-empty subarray of a circular array is one of two kinds — non-wrapping (a normal contiguous segment) or wrapping (it crosses the boundary). The wrapping kind's complement on the circle is itself a non-wrapping subarray. So:

Think of the array as a circle.  Any contiguous subarray is either:
  (a) "Inside" — doesn't wrap.  Plain Kadane handles this.
  (b) "Outside" — wraps around the end.  The COMPLEMENT of (b), in the
       circle, is a contiguous non-wrap subarray.  Maximizing (b) is
       therefore equivalent to MINIMIZING its complement, then taking
       total - (min non-wrap subarray).

So:    answer = max( Kadane(nums), total − minKadane(nums) ).
Then patch the edge case where every element is negative.

Both branches reduce to plain Kadane: one for the max subarray, one for the min subarray (computed by running Kadane on the negated array, then negating the result). Two linear passes, constant space.

Building block: plain Kadane

def kadane(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

Solution

def max_subarray_circular(nums: list[int]) -> int:
    """O(n).  Take the better of:
        (a) the non-wrap maximum (plain Kadane on the array), or
        (b) total - (minimum non-wrap subarray) — which equals the best WRAPPING window.
       Edge case: if ALL elements are negative, (b) returns 0 (empty wrap), which is invalid.
       Then the answer is just (a).
    """
    total = sum(nums)
    best_no_wrap = kadane(nums)
    # Min subarray = -Kadane(-nums)
    min_no_wrap  = -kadane([-x for x in nums])
    if best_no_wrap < 0:                     # all negative -> can't take an empty subarray
        return best_no_wrap
    best_wrap = total - min_no_wrap
    return max(best_no_wrap, best_wrap)

Edge case: all-negative array

If every element is negative, the "minimum non-wrap subarray" is the whole array, and total − total = 0 — which would correspond to the empty subarray. The problem requires non-empty, so we fall back to plain Kadane in that case.

Trace

nums = [5, -3, 5]

total = 7
non-wrap Kadane:           [5, -3, 5] -> best 7 ([5,-3,5])  ✓
min subarray (-Kadane(-)): [-5, 3, -5] -> best 3, so min = -3.
best_wrap = total - min_no_wrap = 7 - (-3) = 10.
return max(7, 10) = 10   (wraps: 5 ... 5).


nums = [-2, -3, -1]
total = -6.
non-wrap Kadane: -1 (single element [-1]).
best_no_wrap < 0 -> return -1 (skip the wrap branch).

Complexity

Time: O(n) — two Kadane passes.
Space: O(n) for the negated array; can be reduced to O(1) by inlining the second Kadane to use -x instead of allocating.

Why "min subarray" isn't a separate problem

Kadane works for both max and min — flip the comparison or run it on negated values. This duality (max of nums ⇔ −min of −nums) is the workhorse that lets the wrap case reduce to a plain Kadane call.