#918 Maximum Sum Circular Subarray

frequently reported atAmazon Google Microsoft

the problem

In plain words

The array is circular: after the last element comes the first one again. Return the largest sum of a non-empty subarray. A subarray may wrap around the end, but it may use each element at most once.

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

out 3

[3] alone.

in nums = [5,-3,5]

out 10

[5, 5]: it wraps from the last element to the first.

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

out -2

Everything is negative, so take the single largest element.

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

A wrapping subarray is the whole array minus one ordinary subarray from the middle. To keep the most, cut out the smallest subarray. So answer = max(normal Kadane, total − minimum subarray) — unless every number is negative.

solutions

From brute force to optimal

From each start, add up to n elements, using % n to wrap, and track the best sum.

For each start: sum = 0.
For len = 1..n: sum += nums[(start + len − 1) % n]; best = max(best, sum).

timeO(n²)

n starts × n lengths = 9·10⁸ steps at n = 3·10⁴ — too slow.

spaceO(1)

A sum and a best.

java

1class Solution {2    public int maxSubarraySumCircular(int[] nums) {3        int n = nums.length, best = Integer.MIN_VALUE;4        for (int start = 0; start < n; start++) {5            int sum = 0;6            for (int len = 1; len <= n; len++) {        // at most n elements: each used once7                sum += nums[(start + len - 1) % n];     // % n wraps past the end to the front8                best = Math.max(best, sum);9            }10        }11        return best;12    }13}

One pass runs two Kadanes — the best subarray and the worst subarray — plus the total.

curMax = max(x, curMax + x); bestMax = max(bestMax, curMax).
curMin = min(x, curMin + x); bestMin = min(bestMin, curMin).
total += x.
If bestMax < 0 return bestMax; else return max(bestMax, total − bestMin).

timeO(n)

One pass with constant work per element.

spaceO(1)

Five variables.

java

1class Solution {2    public int maxSubarraySumCircular(int[] nums) {3        int total = 0;4        int curMax = 0, bestMax = nums[0]; // best subarray that does NOT wrap5        int curMin = 0, bestMin = nums[0]; // worst subarray: cutting it out leaves the best wrap6        for (int x : nums) {7            curMax = Math.max(x, curMax + x);8            bestMax = Math.max(bestMax, curMax);9            curMin = Math.min(x, curMin + x);10            bestMin = Math.min(bestMin, curMin);11            total += x;12        }13        if (bestMax < 0) return bestMax; // all negative: total - bestMin would be the empty subarray14        return Math.max(bestMax, total - bestMin);15    }16}

in the room

How to say it in the interview

talk track

Split the cases: the best subarray either doesn't wrap (plain Kadane) or it wraps.
Draw a wrapping subarray: what it leaves out is a normal subarray in the middle. Keeping the most = leaving out the least.
Handle all-negative before the interviewer asks: then total − min is the empty subarray (0), which isn't allowed.

traps

Forgetting the all-negative case: [-3,-2,-3] would return 0 instead of −2.
Running Kadane on the array written twice: a long subarray could then use the same element twice.

what they ask next

Follow-ups

Is there another O(n) way?

Prefix sums over the doubled array, plus a monotonic deque that keeps the smallest prefix within the last n positions. Correct, but much more code than two Kadanes.

before you submit

Edge cases to test

All negative → the largest single element ([-3,-2,-3] → −2).
One element → that element.
Wrapping is best ([5,-3,5] → 10).
The whole array is the answer — taking every element once is allowed.

practise next