Maximum Sum Circular Subarray

MediumArrays · Kadane’s Algorithm🧩 Kadane's Running Best LeetCode #918 ↗Updated Oct 30, 2026

Problem

You get an integer array nums that is treated as a ring: the element after the last one is the first one again. Return the largest possible sum of a non-empty contiguous piece of this ring, where each position may be used at most once (a piece can wrap around the end, but cannot be longer than n).

Input[1,-2,3,-2]Output3

Input[5,-3,5]Output10 (wraps: 5 + 5)

Input[-3,-2,-3]Output-2

1 ≤ n ≤ 3·10⁴ · -3·10⁴ ≤ nums[i] ≤ 3·10⁴

Try it yourself

Java

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A wrapping piece is the whole ring minus a normal (non-wrapping) middle piece. So the best wrapping sum = total − minimum subarray sum; run Kadane twice (max and min) and take the better answer.

PatternKadane's Running Best

Instinct Best sum or product of a contiguous subarray in one pass? At each index choose - extend the run ending here or restart - and track the global best.

Memory hack Carry the bag only while it helps - a negative past is dead weight, drop it and restart here.

Open the Kadane's Running Best guide →

Approaches

Brute ForceTry Every Start and Length

Time O(n²)Space O(1)

Fix a starting index, then grow the piece one step at a time for up to n elements, reading nums[(start + len) % n]. The running sum is extended in O(1), so every one of the n² pieces is scored.

Java

public int maxSubarraySumCircular(int[] nums) {
    int n = nums.length;
    int best = Integer.MIN_VALUE;
    for (int start = 0; start < n; start++) {
        int sum = 0;
        // grow the piece clockwise, at most n elements
        for (int len = 0; len < n; len++) {
            sum += nums[(start + len) % n];
            best = Math.max(best, sum);
        }
    }
    return best;
}

Correct and simple, but quadratic — too slow at n = 3·10⁴ in tight limits.

BetterKadane + Best Prefix / Suffix Split

Time O(n)Space O(n)

A wrapping piece is a suffix nums[j..n-1] glued to a prefix nums[0..i] with i < j. Precompute bestPrefix[i] = max prefix sum ending at or before i, then sweep suffixes from the right and pair each with bestPrefix[j-1]. Compare with plain Kadane for the non-wrapping case.

Java

public int maxSubarraySumCircular(int[] nums) {
    int n = nums.length;
    // non-wrapping case: classic Kadane
    int best = nums[0], cur = 0;
    for (int x : nums) {
        cur = Math.max(cur + x, x);
        best = Math.max(best, cur);
    }
    // bestPrefix[i] = max sum of nums[0..k] over all k <= i
    int[] bestPrefix = new int[n];
    int run = nums[0];
    bestPrefix[0] = run;
    for (int i = 1; i < n; i++) {
        run += nums[i];
        bestPrefix[i] = Math.max(bestPrefix[i - 1], run);
    }
    // wrapping case: suffix nums[j..n-1] + best prefix ending before j
    int suffix = 0;
    for (int j = n - 1; j >= 1; j--) {
        suffix += nums[j];
        best = Math.max(best, suffix + bestPrefix[j - 1]);
    }
    return best;
}

Linear time, but needs an extra O(n) array.

OptimalDouble Kadane (Total − Min Subarray)

Time O(n)Space O(1)

In one pass track the usual max-subarray sum and the min-subarray sum plus the total. Removing the worst middle piece leaves the best wrapping piece: total − minSum. If every number is negative, that would remove everything (an empty piece), so return maxSum instead.

Java

public int maxSubarraySumCircular(int[] nums) {
    int total = 0;
    int curMax = 0, maxSum = nums[0];
    int curMin = 0, minSum = nums[0];
    for (int x : nums) {
        curMax = Math.max(curMax + x, x);
        maxSum = Math.max(maxSum, curMax);
        curMin = Math.min(curMin + x, x);
        minSum = Math.min(minSum, curMin);
        total += x;
    }
    // all negative: total - minSum would be the empty piece
    if (maxSum < 0) return maxSum;
    return Math.max(maxSum, total - minSum);
}

Dry run[1,-2,3,-2]

i current changed

i=0
5
i
-3

5

max=5 min=5 tot=5
i=1
5

-3
i
5

max=5 min=-3 tot=2
i=2
5

-3

5
i
max=7 min=-3 tot=7
end
5

-3

5

max(7, 7-(-3)) = 10

One pass, constant memory — the standard interview answer.

Pro tip

Say the all-negative edge case out loud before coding — it is the bug interviewers wait for.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Start and Length	`O(n²)`	`O(1)`
Better	Kadane + Best Prefix / Suffix Split	`O(n)`	`O(n)`
Optimal	Double Kadane (Total − Min Subarray)	`O(n)`	`O(1)`

Common pitfalls

Returning total − minSum when all numbers are negative — that is the empty piece (0).
Concatenating the array and running Kadane — allows pieces longer than n.
Initialising maxSum to 0 — wrong for all-negative input.

Interview tips

Split the cases: the answer either wraps or it doesn’t.
Draw the ring: a wrapping piece is the complement of a middle piece.
Mention the prefix/suffix version as a stepping stone if the complement trick doesn’t click.

Pattern

Kadane + complement → circular max-subarray problems: best wrap = total minus worst middle.

My notes saved in this browser