Problem statement

Given a circular integer array nums, return the maximum possible sum of a non-empty subarray.

Circular means the end wraps around to the beginning, so a subarray may run off the end and continue from index 0. No element may be used twice.

Example 1

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: The subarray [3].

Example 2

Input: nums = [5,-3,5]
Output: 10
Explanation: Wrap around: [5] at the end plus [5] at the start.

Example 3

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

Constraints

• 1 <= nums.length <= 40
• -1000 <= nums[i] <= 1000

Hints for Maximum Sum Circular Subarray

1. Hint 1

   A best subarray either stays inside the array or wraps around the ends.

2. Hint 2

   The wrapping case is the total minus the minimum inner subarray, so run Kadane twice — once for the max, once for the min.

3. Hint 3

   Guard the all-negative case: the minimum subarray is then the whole array, and total - minSum would be an empty selection.

How to solve Maximum Sum Circular Subarray

The best subarray either lies inside the array (ordinary Kadane) or wraps around, in which case it is the total minus the minimum inner subarray. Run Kadane for both max and min.

Approach

1. In one pass compute total, the maximum subarray sum and the minimum subarray sum.
2. If the maximum is negative, return it (all elements negative).
3. Otherwise return max(maxSum, total - minSum).

Why it works

A wrapping subarray is the complement of a contiguous inner subarray, so its sum is total - inner; minimising the inner sum maximises the wrap. The all-negative guard prevents choosing the empty complement.

Complexity

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

Pitfalls

• Without the guard, total - minSum is 0 for an all-negative array, but the subarray must be non-empty.

Reference solution

Python

def maxSubarraySumCircular(nums) -> int:
    total = 0
    max_sum = float("-inf")
    cur_max = 0
    min_sum = float("inf")
    cur_min = 0
    for x in nums:
        total += x
        cur_max = max(x, cur_max + x)
        max_sum = max(max_sum, cur_max)
        cur_min = min(x, cur_min + x)
        min_sum = min(min_sum, cur_min)
    if max_sum < 0:
        return max_sum
    return max(max_sum, total - min_sum)

Java

public static int maxSubarraySumCircular(int[] nums) {
    int total = 0;
    int maxSum = -2000000, curMax = 0;
    int minSum = 2000000, curMin = 0;
    for (int x : nums) {
        total += x;
        curMax = Math.max(x, curMax + x);
        maxSum = Math.max(maxSum, curMax);
        curMin = Math.min(x, curMin + x);
        minSum = Math.min(minSum, curMin);
    }
    if (maxSum < 0) return maxSum;
    return Math.max(maxSum, total - minSum);
}

C++

int maxSubarraySumCircular(vector<int>& nums) {
    int total = 0;
    int maxSum = -2000000, curMax = 0;
    int minSum = 2000000, curMin = 0;
    for (int x : nums) {
        total += x;
        curMax = max(x, curMax + x);
        maxSum = max(maxSum, curMax);
        curMin = min(x, curMin + x);
        minSum = min(minSum, curMin);
    }
    if (maxSum < 0) return maxSum;
    return max(maxSum, total - minSum);
}

JavaScript

var maxSubarraySumCircular = function(nums) {
    let total = 0;
    let maxSum = -Infinity, curMax = 0;
    let minSum = Infinity, curMin = 0;
    for (let i = 0; i < nums.length; i++) {
        total += nums[i];
        curMax = Math.max(nums[i], curMax + nums[i]);
        if (curMax > maxSum) maxSum = curMax;
        curMin = Math.min(nums[i], curMin + nums[i]);
        if (curMin < minSum) minSum = curMin;
    }
    if (maxSum < 0) return maxSum;
    return Math.max(maxSum, total - minSum);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium