Largest Sum Subarray in a Circular Array

Hard25–30 min

Topics

ArrayDynamic Programming

Companies

AmazonMicrosoftGoogleBloomberg

Given a CIRCULAR array nums — where the last element connects back around to the first — return the largest possible sum of any non-empty contiguous subarray, allowing the subarray to wrap past the end of the array and continue from the beginning. Trying every wrapped window works, but re-summing each one from scratch wastes the structure of the problem. Every wrap-around subarray is the complement of some ordinary, non-wrapping subarray sitting in the middle — so the best wrap-around sum is just total - (the minimum-sum subarray). Running Kadane's algorithm twice — once for the maximum, once for the minimum — turns an O(n²) search into a single O(n) pass.

Test Case 1:

Input:nums = [5, -3, 5]

Output:10

Explanation:The best subarray wraps around: the last element (5) plus the first element (5), skipping the -3 in the middle.

Test Case 2:

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

Output:3

Explanation:The best subarray here doesn't wrap — it's just [3] on its own.

Test Case 3:

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

Output:-2

Explanation:Every element is negative, so the answer is simply the least-negative single element — an empty selection isn't allowed.

Constraints

◆1 ≤ nums.length ≤ 3×10⁴
◆-3×10⁴ ≤ nums[i] ≤ 3×10⁴

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-8 integers, -10 to 10

1	class Solution {
2	public int maxCircularSubarraySum(int[] nums) {
3	int total = 0, maxSum = nums[0], curMax = 0, minSum = nums[0], curMin = 0;
4	for (int num : nums) {
5	curMax = Math.max(curMax + num, num);
6	maxSum = Math.max(maxSum, curMax);
7	curMin = Math.min(curMin + num, num);
8	minSum = Math.min(minSum, curMin);
9	total += num;
10	}
11	if (maxSum < 0) return maxSum;
12	return Math.max(maxSum, total - minSum);
13	}
14	}
15

-3

Variables

total0

maxSum5

curMax0

minSum5

curMin0

INITIALIZE

Start total at 0, maxSum and minSum at nums[0] = 5, and curMax/curMin at 0. Walk the array once, running Kadane's algorithm for both the maximum and minimum subarray sum at the same time.

Step 1 / 5

Approach & Solutions

Brute Force

Brute

Treat the array as circular by using modulo arithmetic: for every possible start index and every possible length up to n, sum that window (wrapping around the end if needed) and track the best sum seen. Correct, but every window is summed from scratch even though consecutive windows barely differ.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int maxCircularSubarraySum(int[] nums) {
        int n = nums.length;
        int maxSum = nums[0];
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int len = 1; len <= n; len++) {
                sum += nums[(i + len - 1) % n];
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

Optimal — Kadane's Algorithm, Twice

Optimal

There are only two cases for where the best circular subarray can sit. Either it doesn't wrap around — that's the ordinary Kadane's algorithm answer (maxSum). Or it DOES wrap around, which means the elements it skips form a single contiguous block in the middle — so the wrap-around sum is just the array's total minus that middle block's sum, and making the skipped block as negative as possible (a second Kadane's pass tracking the minimum) maximizes what's left. The one exception: if every element is negative, an empty wrap-around selection isn't valid, so just return maxSum directly.

TimeO(n)