214. Maximum Circular Subarray

Why this mechanism works

An optimum either does not wrap, handled by ordinary Kadane, or wraps and therefore excludes one middle interval. Maximizing a wrapped sum is total minus the minimum nonempty subarray sum. If every value is negative, excluding the entire array would create an illegal empty answer, so return the ordinary maximum in that case.

State and boundaries

high_end/low_end summarize maximum/minimum sums ending here. best/worst are their global extrema; total is the full processed sum.

Protocol

1. Initialize extrema from the first value.
2. Update both Kadane recurrences and total.
3. If best<0 return best.
4. Otherwise return max(best,total-worst).

Visualization

[5,-3,5], total=7, minimum middle=-3
wrapped selection: last 5 + first 5
7-(-3)=10

Python implementation

def max_circular_subarray(nums):
    if not nums:
        return None
    high_end = low_end = best = worst = total = nums[0]
    for i in range(1, len(nums)):
        value = nums[i]
        high_end = max(value, high_end + value)
        low_end = min(value, low_end + value)
        best, worst = max(best, high_end), min(worst, low_end)
        total += value
    return best if best < 0 else max(best, total - worst)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 max_circular_subarray: if not nums:
nums=[5, -3, 5]

L4 max_circular_subarray: high_end = low_end = best = worst = total = nums[0]
nums=[5, -3, 5]; high_end=5; low_end=5; best=5; worst=5; total=5

L5 max_circular_subarray: for i in range(1, len(nums)):
nums=[5, -3, 5]; high_end=5; low_end=5; best=5; worst=5; total=5; i=1

L6 max_circular_subarray: value = nums[i]
nums=[5, -3, 5]; high_end=5; low_end=5; best=5; worst=5; total=5; i=1; value=-3

L7 max_circular_subarray: high_end = max(value, high_end + value)
nums=[5, -3, 5]; high_end=2; low_end=5; best=5; worst=5; total=5; i=1; value=-3

L8 max_circular_subarray: low_end = min(value, low_end + value)
nums=[5, -3, 5]; high_end=2; low_end=-3; best=5; worst=5; total=5; i=1; value=-3

L9 max_circular_subarray: best, worst = max(best, high_end), min(worst, low_end)
nums=[5, -3, 5]; high_end=2; low_end=-3; best=5; worst=-3; total=5; i=1; value=-3

L10 max_circular_subarray: total += value
nums=[5, -3, 5]; high_end=2; low_end=-3; best=5; worst=-3; total=2; i=1; value=-3

... 2 intermediate state changes omitted ...

L7 max_circular_subarray: high_end = max(value, high_end + value)
nums=[5, -3, 5]; high_end=7; low_end=-3; best=5; worst=-3; total=2; i=2; value=5

L8 max_circular_subarray: low_end = min(value, low_end + value)
nums=[5, -3, 5]; high_end=7; low_end=2; best=5; worst=-3; total=2; i=2; value=5

L9 max_circular_subarray: best, worst = max(best, high_end), min(worst, low_end)
nums=[5, -3, 5]; high_end=7; low_end=2; best=7; worst=-3; total=2; i=2; value=5

L10 max_circular_subarray: total += value
nums=[5, -3, 5]; high_end=7; low_end=2; best=7; worst=-3; total=7; i=2; value=5

L2 max_circular_subarray: if not nums:
nums=[-3, -2, -5]

L4 max_circular_subarray: high_end = low_end = best = worst = total = nums[0]
nums=[-3, -2, -5]; high_end=-3; low_end=-3; best=-3; worst=-3; total=-3

L5 max_circular_subarray: for i in range(1, len(nums)):
nums=[-3, -2, -5]; high_end=-3; low_end=-3; best=-3; worst=-3; total=-3; i=1

L6 max_circular_subarray: value = nums[i]
nums=[-3, -2, -5]; high_end=-3; low_end=-3; best=-3; worst=-3; total=-3; i=1; value=-2

L7 max_circular_subarray: high_end = max(value, high_end + value)
nums=[-3, -2, -5]; high_end=-2; low_end=-3; best=-3; worst=-3; total=-3; i=1; value=-2

L8 max_circular_subarray: low_end = min(value, low_end + value)
nums=[-3, -2, -5]; high_end=-2; low_end=-5; best=-3; worst=-3; total=-3; i=1; value=-2

L9 max_circular_subarray: best, worst = max(best, high_end), min(worst, low_end)
nums=[-3, -2, -5]; high_end=-2; low_end=-5; best=-2; worst=-5; total=-3; i=1; value=-2

L10 max_circular_subarray: total += value
nums=[-3, -2, -5]; high_end=-2; low_end=-5; best=-2; worst=-5; total=-5; i=1; value=-2

... 2 intermediate state changes omitted ...

L7 max_circular_subarray: high_end = max(value, high_end + value)
nums=[-3, -2, -5]; high_end=-5; low_end=-5; best=-2; worst=-5; total=-5; i=2; value=-5

L8 max_circular_subarray: low_end = min(value, low_end + value)
nums=[-3, -2, -5]; high_end=-5; low_end=-10; best=-2; worst=-5; total=-5; i=2; value=-5

L9 max_circular_subarray: best, worst = max(best, high_end), min(worst, low_end)
nums=[-3, -2, -5]; high_end=-5; low_end=-10; best=-2; worst=-10; total=-5; i=2; value=-5

L10 max_circular_subarray: total += value
nums=[-3, -2, -5]; high_end=-5; low_end=-10; best=-2; worst=-10; total=-10; i=2; value=-5

Why the solution is correct

Every proper wrapped interval is the complement of a nonempty ordinary interval, so the minimum excluded sum gives its largest value. Nonwrapped candidates are covered separately. The all-negative guard prevents the only case where the invalid empty complement would exceed every legal answer; otherwise a legal ordinary answer handles that boundary.

Time and space

O(n) time and O(1) auxiliary numeric state.

Common mistakes

Returning total-worst unconditionally gives zero on all-negative input. Allowing repeated laps changes the problem and can make positive totals unbounded.

Reasoning card

Transfer exercise

Return the wrapped interval as either one ordinary range or two ranges at the array ends.