Maximum Sum Circular Subarray

Difficulty: Medium Source: NeetCode

Problem

Given a circular integer array nums (last element wraps to first), return the maximum possible sum of a non-empty subarray of nums.

Example 1: Input: nums = [1, -2, 3, -2] Output: 3

Example 2: Input: nums = [5, -3, 5] Output: 10

Example 3: Input: nums = [-3, -2, -3] Output: -2

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Maximum Subarray (Kadane’s) — the non-circular version is a building block
• Complement thinking — the circular max relates to the total sum and the minimum subarray

1. Brute Force

Intuition

For each starting position i, compute the sum of every subarray that wraps around or doesn’t. To simulate circularity, we can double the array and run Kadane’s on it. But even simpler: for each starting index, sum in a sliding window of length up to n. This is O(n²).

Algorithm

1. Double the array: doubled = nums + nums.
2. For each start i from 0 to n-1:
   • Sum all subarrays doubled[i:i+k] for k from 1 to n.
   • Track the maximum.
3. Return the maximum.

Solution

def maxSubarraySumCircular(nums):
    n = len(nums)
    doubled = nums + nums
    max_sum = float('-inf')

    for i in range(n):
        running = 0
        for j in range(i, i + n):
            running += doubled[j]
            max_sum = max(max_sum, running)

    return max_sum


print(maxSubarraySumCircular([1, -2, 3, -2]))    # 3
print(maxSubarraySumCircular([5, -3, 5]))         # 10
print(maxSubarraySumCircular([-3, -2, -3]))       # -2

Complexity

• Time: O(n²)
• Space: O(n) — doubled array

2. Greedy — Total Sum Minus Minimum Subarray

Intuition

A subarray in a circular array either:

1. Does not wrap around — this is just the regular max subarray (Kadane’s).
2. Wraps around — the subarray covers the start and end of the array.

For case 2, the elements not in the subarray form a contiguous middle section. So the circular max = total_sum - min_subarray_sum. We want to maximise the kept portion, which means minimising what we throw away.

Run Kadane’s twice:

• Once for max subarray (case 1).
• Once for min subarray (case 2).

Answer = max(max_sub, total - min_sub).

Edge case: if all elements are negative, min_sub == total, meaning we’d be returning 0 for case 2. But the answer must be non-empty, so we take max_sub in that case (the least negative single element).

Algorithm

1. Compute total = sum(nums).
2. Run Kadane’s for max_sub.
3. Run Kadane’s (minimising) for min_sub.
4. If max_sub < 0, return max_sub (all negatives edge case).
5. Return max(max_sub, total - min_sub).

Solution

def maxSubarraySumCircular(nums):
    def kadane_max(arr):
        cur = best = arr[0]
        for num in arr[1:]:
            cur = max(num, cur + num)
            best = max(best, cur)
        return best

    def kadane_min(arr):
        cur = best = arr[0]
        for num in arr[1:]:
            cur = min(num, cur + num)
            best = min(best, cur)
        return best

    total = sum(nums)
    max_sub = kadane_max(nums)
    min_sub = kadane_min(nums)

    # Edge case: all negative, circular answer would be 0 (empty), but must be non-empty
    if max_sub < 0:
        return max_sub

    return max(max_sub, total - min_sub)


print(maxSubarraySumCircular([1, -2, 3, -2]))    # 3
print(maxSubarraySumCircular([5, -3, 5]))         # 10
print(maxSubarraySumCircular([-3, -2, -3]))       # -2
print(maxSubarraySumCircular([3, -1, 2, -1]))     # 4
print(maxSubarraySumCircular([3, -2, 2, -3]))     # 3

Complexity

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

Common Pitfalls

Returning total - min_sub when all elements are negative. If all elements are negative, min_sub == total, so total - min_sub = 0. But a subarray must be non-empty — the correct answer is the maximum single element (which Kadane’s max gives us). Always check if max_sub < 0.

Using Kadane’s on a doubled array without capping length. If you run Kadane’s on nums + nums without restricting to n elements, you might pick a subarray longer than n — which isn’t a valid circular subarray.

Forgetting that case 2 can’t be the entire array. total - min_sub requires that min_sub be a proper non-empty subarray. If min_sub is the entire array, the “kept” portion is empty — which is invalid. The all-negative edge case catches this.