Maximum Sum Circular Subarray
Medium · Arrays & Hashing · Array · Dynamic Programming · Divide and Conquer · Queue · Monotonic Queue
Problem
The integer array nums is circular: after the last element comes the first one again. Return the largest sum of a non-empty subarray.
A subarray may run past the end and continue from the start, but it may use each element at most once, so it is never longer than nums.
Examples
Input: nums = [4,-6,3,-1,5] Output: 11
From index 2 around to index 0: 3 - 1 + 5 + 4 = 11.
Input: nums = [-4,-2,-7] Output: -2
Every element is negative, so the best subarray is the single element -2.
Input: nums = [2,-1,3] Output: 5
The wrapping subarray [3, 2] leaves out the -1 and sums to 5.
Constraints
- n == len(nums)
- 1 <= n <= 3 · 10^4
- -3 · 10^4 <= nums[i] <= 3 · 10^4
Approaches
- Baseline: every start, every length — time O(n²), space O(1)
Follow-up
If the subarray length were limited to at most k, the complement trick no longer applies. Double the array, take prefix sums, and for each end keep the smallest prefix sum within the last k positions with a monotonic deque: O(n).
Related problems
Start free on Cariara · Coding problems · System design studio
