Maximum Sum Circular Subarray

1. Define the problem

Given a circular integer array nums of length n, where the array wraps around so that the element after nums[n - 1] is nums₀, return the maximum possible sum of a non-empty subarray of nums. A subarray may only include each element of nums at most once, but it is allowed to wrap around the end of the array. The best subarray is either a normal, non-wrapping run — found with ordinary Kadane's — or it wraps around, which is equivalent to total sum minus the minimum subarray sum , found with a second, minimum-tracking Kadane's pass.

Constraints

n == nums.length
1 ≤ n ≤ 3 × 10⁴
-3 × 10⁴ ≤ nums_i ≤ 3 × 10⁴

Example

Inputnums = [5, -3, 5]

Output10

Explanation Wrapping around and skipping -3, the subarray [5, 5] (last element then first element) sums to 10.

2. Know the words first

In plain terms

Ordinary Kadane's: The standard running-sum pass that finds the maximum sum of a contiguous, non-wrapping subarray.
Total sum minus the minimum subarray sum: Removing the worst contiguous stretch from the middle of the array leaves the best possible wrap-around subarray, made of everything else — found by running Kadane's a second time to track the minimum instead of the maximum.

3. Visualize the solution

Run two Kadane passes at once: one for max, one for min

1-3

StatusmaxSum: 5 · minSum: 5 · total: 5

Seed both running passes and the total with the first element, 5.

What happens in this step

nums[0] = 5

curMax = max(curMax + num, num) = max(0 + 5, 5) = 5   →  maxSum = max(-∞, 5) = 5
curMin = min(curMin + num, num) = min(0 + 5, 5) = 5   →  minSum = min(∞, 5) = 5
total = 0 + 5 = 5

Seed both running passes and the total with the first element.

Step 1 of 4

Steps to visualize

Run ordinary Kadane's to track the best non-wrapping subarray sum (maxSum).
At the same time, run a mirrored Kadane's that tracks the worst (minimum) subarray sum (minSum).
Also keep a running total of the whole array.
If maxSum is negative, every value is negative, so the answer is just maxSum — a wrap-around subarray would have to be empty, which is not allowed.
Otherwise, the answer is the larger of maxSum and total minus minSum, since removing the worst stretch leaves the best wrap-around subarray.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Run two Kadane passes at once: one for max, one for min

1-3

StatusmaxSum: 5 · minSum: 5 · total: 5

Seed both running passes and the total with the first element, 5.

What happens in this step

nums[0] = 5

curMax = max(curMax + num, num) = max(0 + 5, 5) = 5   →  maxSum = max(-∞, 5) = 5
curMin = min(curMin + num, num) = min(0 + 5, 5) = 5   →  minSum = min(∞, 5) = 5
total = 0 + 5 = 5

Seed both running passes and the total with the first element.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function maxSubarraySumCircular(nums) {
  let total = 0;
  let curMax = 0;
  let maxSum = -Infinity;
  let curMin = 0;
  let minSum = Infinity;

  for (const num of nums) {
    curMax = Math.max(curMax + num, num);
    maxSum = Math.max(maxSum, curMax);

    curMin = Math.min(curMin + num, num);
    minSum = Math.min(minSum, curMin);

    total += num;
  }

  if (maxSum < 0) {
    return maxSum;
  }

  return Math.max(maxSum, total - minSum);
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, -2, 3, -2]`	`3`	example from the docstring family — wrapping does not help here
`nums = [5, -3, 5]`	`10`	the wrap-around subarray beats every non-wrapping one
`nums = [-3, -2, -3]`	`-2`	every value negative — wrapping is disallowed since the array must stay non-empty
`nums = [5]`	`5`	smallest valid input, a single positive element
`nums = [-1]`	`-1`	smallest valid input, a single negative element
`nums = [1, 2, 3]`	`6`	every value positive — the whole array wins without needing to wrap
`nums = [3, -1]`	`3`	boundary case, exactly two elements
`nums = [-1, -1]`	`-1`	repeated negative values with no positive option at all

Maximum Sum Circular Subarray