Maximum Sum Circular Subarray

Given an integer array nums, return the maximum sum of a non-empty contiguous subarray in the circular array.

In a circular array, the element after the last position is the first element.

Return 0 when nums is empty.

Brute Force Approach

A circular subarray can begin at any index and continue forward, wrapping to the beginning when the array ends.

The direct approach starts from every position and extends the subarray one element at a time. Limiting the length to n prevents any element from being selected more than once.

Algorithm

• Store the array size in n. If n == 0, return 0 because no non-empty subarray can be formed.

• Initialize maxSum with nums[0], ensuring that arrays containing only negative values still return a valid non-empty subarray sum.

• Treat every index start as the beginning of a circular subarray and initialize currentSum with 0 for that starting position.

• Extend the subarray from length 1 through n. For each length, calculate the next index as (start + length - 1) % n, where modulo allows the traversal to wrap from the end of the array back to the beginning.

• Add the selected element to currentSum and compare it with maxSum after every extension because each length represents one valid circular subarray.

• Return maxSum after every starting position and every valid length have been examined.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every starting position extends through at most N elements.

Space Complexity: O(1), because only loop indices, currentSum, and maxSum require auxiliary storage.

Better Approach

A wrapping subarray contains two connected parts: a prefix from the beginning and a suffix from the end.

The best suffix available after every prefix boundary can be prepared in advance. Combining each prefix with the best non-overlapping suffix finds the strongest wrapping sum. The normal maximum subarray must also be checked because the answer may not wrap.

Algorithm

• Store the array size in n. If the array is empty, return 0.

• Find normalMax using Kadane’s Algorithm, since the maximum-sum subarray may lie completely inside the normal array without wrapping.

• Create maxSuffix, where maxSuffix[index] stores the greatest suffix sum obtainable by starting at index or at any position after it.

• Build suffix sums from right to left and update maxSuffix so that each position remembers the strongest suffix available from that point onward.

• Traverse possible prefix endings from index 0 to n - 2. Maintain the current prefix sum and combine it with maxSuffix[index + 1], ensuring that the selected prefix and suffix remain separate and do not overlap.

• Return the larger value between normalMax and the best prefix-suffix combination, covering both non-wrapping and wrapping subarrays.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Kadane’s traversal, suffix construction, and prefix-suffix combination each require linear time.

Space Complexity: O(N), because maxSuffix stores one value for every array index.

Optimal Approach

The maximum circular subarray can appear in two forms.

The first form is a normal subarray that does not cross the array boundary. Kadane’s Algorithm finds this value directly.

The second form wraps around the boundary. Such a subarray keeps the beginning and end of the array while excluding one middle section. Removing the minimum-sum subarray from the total sum therefore leaves the maximum wrapping sum.

Algorithm

• Store the array size in n. If n == 0, return 0.

• Initialize totalSum, currentMax, maxSum, currentMin, and minSum with nums[0]. The maximum states track the best normal subarray, while the minimum states track the middle section that may be excluded for a wrapping result.

• Traverse from index 1, since the first element has already been included in all initial states.

• Add the current value to totalSum. Update currentMax using the better choice between starting fresh from the current element and extending the previous maximum-ending subarray. Update maxSum with the best value seen so far.

• Similarly, update currentMin using the smaller choice between starting fresh and extending the previous minimum-ending subarray, then update minSum.

• If maxSum < 0, return maxSum because every element is negative and removing the complete minimum subarray would incorrectly create an empty result. Otherwise, calculate totalSum - minSum as the best wrapping sum and return the larger of the wrapping and normal sums.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Every element is processed once using constant-time updates.

Space Complexity: O(1), because only totalSum, currentMax, maxSum, currentMin, and minSum require auxiliary storage.

FAQs

Q1. Why does totalSum - minSum represent the maximum wrapping sum?

A wrapping subarray keeps elements from the end and beginning of the array. The only excluded elements form one contiguous middle subarray. Removing the smallest possible middle sum leaves the largest wrapping sum.

Q2. Why must the all-negative case be handled separately?

When every value is negative, the minimum subarray is the complete array. Subtracting that sum from totalSum gives 0, which represents selecting no elements and violates the non-empty requirement.

Q3. Why is the normal maximum subarray still required?

The strongest subarray may remain completely inside the array without crossing the circular boundary. The final answer must compare both normal and wrapping possibilities.

Q4. Can a valid circular subarray contain an element more than once?

No. A circular subarray may wrap from the last index to the first, but its length cannot exceed n. Allowing a greater length would reuse array elements.

Q5. How can the actual circular subarray indices be returned?

Track the boundaries of the normal maximum and minimum subarrays. For the wrapping case, the answer contains all indices outside the minimum-sum range.

Q6. Can the Optimal Approach work when exactly one element is present?

Yes. Both the normal maximum and minimum equal that element. The all-negative check or the normal maximum comparison ensures that the single element is returned correctly.