LeetCode 918: Maximum Sum Circular Subarray

Problem Restatement

We are given a circular integer array nums.

A circular array means the element after the last element is the first element again.

We need to find the maximum possible sum of a non-empty subarray.

A subarray may:

• Stay completely inside the array
• Or wrap around the end back to the beginning

Each element can only be used once.

The official problem statement defines circular subarrays this way. (leetcode.com)

Input and Output

Function shape:

def maxSubarraySumCircular(nums: list[int]) -> int:
    ...

Examples

Example 1:

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

Best subarray:

[3]

Answer:

3

Example 2:

nums = [5, -3, 5]

The best subarray wraps around:

[5] + [5]

Sum:

10

Answer:

10

Example 3:

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

The best subarray is:

[-2]

Answer:

-2

First Thought: Try Every Circular Subarray

A direct method is:

1. Choose every possible start index.
2. Extend the subarray around the circle.
3. Compute every possible sum.

This works, but there are too many subarrays.

The time complexity becomes quadratic.

We need a linear-time approach.

Key Insight

There are two possible types of optimal subarrays.

Case 1: Normal Subarray

The best subarray does not wrap around.

Then the problem becomes the classic maximum subarray problem solved by Kadane’s algorithm.

Example:

[1, -2, 3, -2]

Best normal subarray:

[3]

Case 2: Circular Subarray

The best subarray wraps around.

Example:

[5, -3, 5]

The best circular subarray uses:

last 5 + first 5

Instead of directly finding the wrapped subarray, think about what gets excluded.

The wrapped subarray equals:

total_sum - middle_subarray

The excluded middle part should have the smallest possible sum.

So:

best_circular = total_sum - minimum_subarray_sum

Important Edge Case

Suppose all numbers are negative.

Example:

[-3, -2, -3]

Then:

minimum_subarray_sum = total_sum

So:

total_sum - minimum_subarray_sum = 0

But 0 is invalid because the subarray must be non-empty.

In this situation, the correct answer is simply the maximum element, which Kadane already gives.

So:

• If the maximum normal subarray sum is negative, return it directly.
• Otherwise, return the larger of:
  • normal maximum
  • circular maximum

Algorithm

1. Use Kadane’s algorithm to find:
   • Maximum subarray sum
2. Use a modified Kadane’s algorithm to find:
   • Minimum subarray sum
3. Compute:
   • total_sum
4. If the maximum subarray sum is negative:
   • Return it
5. Otherwise:
   • Return:

max(max_subarray_sum, total_sum - min_subarray_sum)

Kadane’s Algorithm

Normal Kadane:

current_max = max(num, current_max + num)
best_max = max(best_max, current_max)

Minimum version:

current_min = min(num, current_min + num)
best_min = min(best_min, current_min)

Correctness

Any optimal circular subarray belongs to one of two categories.

If it does not wrap around the array boundary, then it is a normal subarray. Kadane’s algorithm correctly computes the maximum such sum.

If it wraps around, then the selected elements consist of a suffix and a prefix of the array. The elements not selected form one contiguous middle subarray.

Therefore:

wrapped_sum = total_sum - excluded_middle_sum

To maximize the wrapped sum, we must minimize the excluded middle sum. The modified Kadane algorithm correctly computes the minimum subarray sum.

So the best wrapped subarray sum is:

total_sum - min_subarray_sum

The algorithm compares the best normal subarray and the best wrapped subarray, so it considers every possible optimal solution.

If all numbers are negative, then the minimum subarray equals the entire array. Subtracting it from the total gives zero, which would represent an empty subarray and is invalid. In this case, the maximum normal subarray is the correct answer.

Therefore, the algorithm always returns the maximum valid circular subarray sum.

Complexity

Implementation

class Solution:
    def maxSubarraySumCircular(self, nums: list[int]) -> int:
        total_sum = 0

        current_max = 0
        best_max = nums[0]

        current_min = 0
        best_min = nums[0]

        for num in nums:
            total_sum += num

            current_max = max(num, current_max + num)
            best_max = max(best_max, current_max)

            current_min = min(num, current_min + num)
            best_min = min(best_min, current_min)

        if best_max < 0:
            return best_max

        return max(best_max, total_sum - best_min)

Code Explanation

Track the total array sum:

total_sum = 0

The maximum subarray logic is standard Kadane:

current_max = max(num, current_max + num)
best_max = max(best_max, current_max)

current_max means:

best subarray ending at current position

The minimum version works similarly:

current_min = min(num, current_min + num)
best_min = min(best_min, current_min)

At the end:

total_sum - best_min

gives the best wrapped subarray sum.

If all numbers are negative:

if best_max < 0:
    return best_max

Otherwise compare both cases:

return max(best_max, total_sum - best_min)

Testing

def run_tests():
    s = Solution()

    assert s.maxSubarraySumCircular([1, -2, 3, -2]) == 3
    assert s.maxSubarraySumCircular([5, -3, 5]) == 10
    assert s.maxSubarraySumCircular([-3, -2, -3]) == -2
    assert s.maxSubarraySumCircular([3, -1, 2, -1]) == 4
    assert s.maxSubarraySumCircular([3, -2, 2, -3]) == 3
    assert s.maxSubarraySumCircular([2, 2, 2]) == 6
    assert s.maxSubarraySumCircular([-1]) == -1

    print("all tests passed")

run_tests()

Test meaning: