Maximum Sum Circular Subarray
Mahabharata — The Circular Chakravyuha — Finding the Strongest Arc in the Spiral Formation
चक्रे यः खण्डः श्रेष्ठः स आदितः अन्ततः मिलेत्। मध्यमं दुर्बलं त्यक्त्वा अंत्यादितौ जोडयेत्॥
*The strongest arc of the circle may begin at the end and finish at the start. Abandon the weak middle — join the end to the beginning.*
The Story
The Chakravyuha was not just a spiral — it was a CIRCLE. Drona's formation wrapped around itself, and the strongest defensive arc might span the seam where the end connected back to the beginning.
General Dhrishtadyumna studied the circular formation's strength values: `[1, -2, 3, -2]`. Each position had a value — positive for strong, negative for weak. He needed the maximum sum of any contiguous arc, including arcs that wrapped around the circle's seam.
"In a linear array," Vidura said, "Kadane gives the answer. But in a circular array, there are two types of subarrays:"
**Case 1: The optimal subarray does NOT wrap around.** Solve with standard Kadane. For `[1,-2,3,-2]`: maxSum = 3.
**Case 2: The optimal subarray DOES wrap around.** A wrap-around subarray is everything EXCEPT some contiguous middle part. If the wrap-around subarray has sum W, and the total array sum is T, then the excluded middle has sum T - W. To MAXIMIZE W, we must MINIMIZE the excluded middle.
So Case 2's answer = `total_sum - minimum_subarray_sum`.
For `[1,-2,3,-2]`: total=0, minSubarraySum = Kadane min = -4 (subarray [-2+3-5]... let me recalculate: [-2]=-2, [-2+3-2]=-1, [3-2]=1, so minSum=-2). Case 2: 0-(-2)=2. Not better than Case 1's 3.
Final answer = max(Case1=3, Case2=2) = **3**.
Dhrishtadyumna tried `[5, -3, 5]`: total=7, Kadane max=10 (entire array!), Kadane min=-3. Case 1: 10. Case 2: 7-(-3)=10. Both give 10. Answer = 10.
"But there's one edge case," Vidura warned. "If ALL elements are negative, the minimum subarray sum = total sum (the entire array). Then Case 2 = total - total = 0. But the answer must be non-empty! An empty subarray (sum=0) is not valid."
"So if Case 1 is negative (all elements negative), we must ignore Case 2 and just return the maximum single element (which is what standard Kadane returns for all-negative arrays)."
"Implementation: if maxSum (Kadane) is negative, return maxSum. Otherwise, return max(maxSum, total-minSum)."
Dhrishtadyumna traced through `[-3, -2, -3]`: - Kadane max = -2 (single element) - Total = -8 - Kadane min = -8 (entire array) - Case 2 = -8 - (-8) = 0 (empty subarray — invalid!) - Since maxSum=-2 < 0: return -2.
"The entire Chakravyuha is weak," Dhrishtadyumna concluded. "The strongest arc is just one position, value -2."
"The circular array forces us to think about what's NOT included," Vidura summarized. "The wrap-around subarray is defined by its complement — the minimum subarray in the middle that we exclude. Total minus minimum interior = maximum circular arc."
This is Kadane's Algorithm extended for circular arrays.
Dhrishtadyumna's First Instinct
Try every start and length in the circular array (using modulo). Compute sum. Track maximum. O(n²) time.
public int maxSubarraySumCircularBruteForce(int[] nums) {
int n = nums.length;
int maxSum = Integer.MIN_VALUE;
for (int start = 0; start < n; start++) {
int sum = 0;
for (int len = 1; len <= n; len++) {
int idx = (start + len - 1) % n;
sum += nums[idx];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}Vidura's Circular Wisdom
public int maxSubarraySumCircular(int[] nums) {
int total = 0;
int maxSum = nums[0], curMax = 0;
int minSum = nums[0], curMin = 0;
for (int n : nums) {
total += n;
// Kadane for maximum subarray
curMax = Math.max(n, curMax + n);
maxSum = Math.max(maxSum, curMax);
// Kadane for minimum subarray
curMin = Math.min(n, curMin + n);
minSum = Math.min(minSum, curMin);
}
// Case 1: non-wrap = maxSum
// Case 2: wrap = total - minSum (exclude the minimum middle)
// Edge: if all negative, maxSum < 0, return maxSum (avoid empty subarray)
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().maxSubarraySumCircular(new int[]{1,-2,3,-2})); // 3
System.out.println(new Solution().maxSubarraySumCircular(new int[]{5,-3,5})); // 10
System.out.println(new Solution().maxSubarraySumCircular(new int[]{-3,-2,-3})); // -2
}Step-by-Step Walkthrough
nums = [3, -1, 2, -1] total = 3 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Kadane max pass: n=3: curMax=3, maxSum=3 n=-1: curMax=2, maxSum=3 n=2: curMax=4, maxSum=4 n=-1: curMax=3, maxSum=4 maxSum = 4 (subarray [3,-1,2]) Kadane min pass: n=3: curMin=3, minSum=3 n=-1: curMin=-1, minSum=-1 n=2: curMin=1, minSum=-1 n=-1: curMin=-1, minSum=-1 minSum = -1 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ maxSum=4 > 0 → return max(4, total-minSum) = max(4, 3-(-1)) = max(4,4) = 4 ✅ Return 4 (Both wrap and non-wrap give 4 here: [3,-1,2] = 4, or [2,-1,3] wrap = 4)
Deep Insight
**The wrap-around insight:** A circular subarray that wraps = total_array - (a non-wrapping subarray in the middle). To maximize the wrap, minimize the middle. Max wrap = total - minSubarray.
**Why `maxSum > 0` for the edge case check?** If all elements are negative, minSum = total (the minimum is the entire array). Case 2 = total - total = 0. But the problem requires at least one element. Return maxSum (the least negative element).
Alternatively, check if `total - minSum == 0` (would mean the entire array is the minimum, so the wrap-around subarray is empty).
**Can maxSum = 0?** If there are zeros in the array, maxSum could be 0. But `maxSum > 0` check would then skip Case 2. This is fine: if maxSum=0, Case 2 = total - minSum ≥ 0 ≥ maxSum=0. We might miss Case 2. Better check: `if maxSum == total` (meaning minSubarray = entire array), return maxSum. Or simply: `return total == minSum ? maxSum : max(maxSum, total - minSum);`
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All circular subarrays checked |
| Optimal | O(n) | O(1) | Single pass for total, maxSum, minSum simultaneously |
Pattern Recognition
✅ Maximum subarray in a CIRCULAR array ✅ Two cases: non-wrapping (standard Kadane) + wrapping (total - minSum) ✅ All-negative edge case: return maxSum directly ✅ Run both Kadane variants in same pass **LeetCode Trigger Phrases:** → "circular array" + maximum subarray sum → "subarray can wrap around" from end to beginning → "contiguous subarray" + "treated as circular"
Bhagavad Gita 13.13
अनादिमत्परं ब्रह्म न सत्तन्नासदुच्यते। सर्वतः पाणिपादं तत् सर्वतोऽक्षिशिरोमुखम्॥
The supreme Brahman has no beginning, no end — it is neither being nor non-being. Yet it has hands and feet everywhere, eyes and heads in all directions.
Connection: The circular array has no fixed start or end — like the infinite Brahman described in the Gita, which extends in all directions with neither first nor last. The wrap-around subarray crosses the artificial boundary we placed at index 0, just as the divine transcends all human-imposed demarcations. The algorithm reveals that the strongest arc might span this 'seam' — the meeting point of end and beginning — just as supreme reality encompasses all apparent opposites.