DP — Maximum Sum Circular Subarray
↗ LeetCode: Maximum Sum Circular Subarray · Medium · pattern chapter →
Max subarray sum in a circular array.
Example 1 — nums=[1,-2,3,-2] → 3 ([3], no wrap) Example 2 — nums=[5,-3,5] → 10 (wrap: [5]…[5]) Example 3 — nums=[-3,-2,-3] → -2 (all-negative: must return single largest)
Constraints — 1 ≤ n ≤ 3·10⁴. Brute is O(n²) doubled-array Kadane — 10⁹ ops = TLE. Two-Kadane trick is O(n) = 3·10⁴ ops = <1ms.
⏱️Interview timer00:00
Approach 1 — Brute doubled-array Kadane
Intuition. Concatenate nums with itself, then run Kadane restricted to windows of size ≤ n. O(n²).
Complexity — Time O(n²); Space O(n). TLE past n=3000. In an interview say "wrap-around = complement of a non-wrap minimum subarray → two-pass Kadane on max and min → O(n)."
Approach 2 — Kadane on both max and min (canonical)
Insight. Answer is either:
- Non-wrapping: standard Kadane max.
- Wrapping:
totalSum − minSubarraySum(peel off the worst middle chunk).
Edge case. If all negative, total − minSubSum = 0 (empty subarray) → return kadaneMax instead.
int maxSubarraySumCircular(int[] nums) {
int total = 0, curMax = 0, curMin = 0, maxS = nums[0], minS = nums[0];
for (int x : nums) {
total += x;
curMax = Math.max(curMax + x, x);
maxS = Math.max(maxS, curMax);
curMin = Math.min(curMin + x, x);
minS = Math.min(minS, curMin);
}
return maxS > 0 ? Math.max(maxS, total - minS) : maxS;
}2
3
4
5
6
7
8
9
10
11
Complexity — Time O(n); Space O(1). Say aloud in an interview: "same cyclic-to-linear reduction as House Robber II — two linear DPs cover both regimes."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Doubled Kadane | O(n²) | O(n) | TLE past n=3000 |
| Kadane × 2 + edge | O(n) | O(1) | Canonical |
When to use which
- Circular → dual Kadane.
- Linear → standard Kadane.
- "Return the subarray" → track indices.