Maximum Sum Circular Subarray

• Difficulty: Medium
• Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue
• Link: https://leetcode.com/problems/maximum-sum-circular-subarray/

Problem Description

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example 1:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

Constraints:

• n == nums.length
• 1 <= n <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104

Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem

Technical Version:
Given a circular array nums of length n, find the maximum sum of any non-empty contiguous subarray under the constraint that no element is included more than once. Formally, for indices i and j (0-based) with length l (1 ≤ l ≤ n), the subarray consists of elements nums[i], nums[(i+1) % n], ..., nums[(i+l-1) % n] where all indices modulo n are distinct. The circular nature means nums[n-1] is adjacent to nums[0]. The goal is to compute max(Σ(nums[(i+k) % n] for k in [0, l-1])) over all valid i and l.

Beginner Version:
Imagine numbers arranged in a circle. You can pick any consecutive segment along the circle, but you cannot go around more than once (so you cannot pick the same number twice). What is the largest possible sum of such a segment?

Mathematical Version:
Let S = Σ_{i=0}^{n-1} nums[i]. Define two linear subarray problems:

• M_max = max_{0 ≤ i ≤ j < n} Σ_{k=i}^{j} nums[k] (standard maximum subarray sum).
• M_min = min_{0 ≤ i ≤ j < n} Σ_{k=i}^{j} nums[k] (minimum subarray sum).
  Then the maximum circular subarray sum is:

$$\text{ans} = \begin{cases} M_{\text{max}} & \text{if } M_{\text{max}} \le 0 \\ \max(M_{\text{max}}, S - M_{\text{min}}) & \text{otherwise} \end{cases}$$

The second case (S - M_min) represents the sum of a wrap-around subarray (suffix + prefix), which is total minus the sum of the excluded contiguous middle segment.

Constraint Analysis

• n == nums.length, 1 <= n <= 3 * 10^4:
  • Limits algorithmic complexity: O(n²) brute force (~9×10⁸ operations) is infeasible; need O(n) or O(n log n).
  • Implies memory usage should be efficient; O(n) extra space is acceptable but O(n²) is not.
• -3 * 10^4 <= nums[i] <= 3 * 10^4:
  • Sums stay within ±9×10⁸, fitting in 32-bit signed integers (max 2.147×10⁹).
  • No overflow issues in most languages if using 64-bit integers, but 32-bit suffices.

Hidden Edge Cases:

• All negative numbers: Maximum sum is the largest (least negative) element. The wrap-around computation S - M_min yields 0 (invalid empty subarray), so must fall back to M_max.
• All positive numbers: Maximum sum is the total sum S. Both linear and wrap-around give S.
• Single element: The element itself is the answer.
• Mixed signs with zero: Zero can be a valid maximum sum (e.g., [0, -1, 0]).
• Wrap-around beats linear: Example [5, -3, 5] where linear max is 7 but wrap-around gives 10.
• Minimum subarray is the entire array: Happens when all numbers are negative; then M_min = S, making S - M_min = 0.
• Minimum subarray is a single negative element: Then S - M_min might be larger than M_max if the excluded element is very negative.

---

2. Intuition Scaffolding

Generate 3 Analogies

1. Real-World Metaphor – Circular Buffet Table:
   Dishes with varying values (positive: delicacies, negative: chores) are placed on a circular table. You can take a consecutive sequence of dishes but cannot go around twice. To maximize your net pleasure, either take a contiguous section of great dishes (linear case) or avoid a section of awful dishes and take the rest (wrap-around case).

2. Gaming Analogy – RPG Circular Dungeon:
   Each room in a circular dungeon has gold (positive) or monsters (negative). You can enter at any room and proceed consecutively, but cannot re-enter a room. Your best strategy is either to clear a linear stretch of treasure-rich rooms or, if the dungeon overall has more gold than monsters, skip the most monster-infested segment and take the remaining rooms (which requires wrapping from end to start).

3. Math Analogy – Arc Sum on a Circle:
   Plot the numbers on a circle. The sum of a subarray corresponds to an arc sum. The maximum arc sum is either a contiguous arc that doesn’t cover the whole circle (linear max) or the complement of a contiguous arc that doesn’t cover the whole circle (total minus minimal arc). This duality reduces the problem to finding both maximum and minimum subarray sums on a line.

Common Pitfalls Section

1. Ignoring wrap-around: Assuming Kadane’s linear solution suffices (fails on [5,-3,5]).
2. Double array with unrestricted Kadane: Concatenating nums to itself and applying Kadane may pick subarrays longer than n, violating the “no duplicate elements” rule.
3. Mis-handling all negatives: Using max(M_max, S - M_min) directly returns 0 for all-negative arrays, which is invalid (empty subarray).
4. Confusing minimum element with minimum subarray sum: The minimum subarray sum could be longer than one element (e.g., [1, -2, -3] has M_min = -5).
5. O(n²) starting-point Kadane: Running Kadane from each starting index is O(n²), too slow for n=30,000.
6. Assuming wrap-around always exists: The wrap-around subarray is valid only if the excluded middle part is not the entire array; otherwise, the wrap-around is empty.
7. Overlooking zero sums: When M_max = 0 (e.g., [0, -1]), it’s a valid answer; not to be confused with the invalid zero from all-negative wrap-around.

---

3. Approach Encyclopedia

Brute Force

Idea: Enumerate all subarrays by starting index i and length l (1 ≤ l ≤ n), compute sum by traversing circularly.

def maxSubarraySumCircular_brute(nums):
    n = len(nums)
    max_sum = float('-inf')
    for i in range(n):
        current_sum = 0
        for l in range(1, n+1):
            j = (i + l - 1) % n
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
    return max_sum

Complexity Proof:

• Time: O(n²) from nested loops. For n=30,000, ≈ 9×10⁸ operations.
• Space: O(1) extra.
  Visualization:

Circle: [a0, a1, a2, ..., a{n-1}]
Check all arcs: 
  Start at 0: arcs of length 1..n
  Start at 1: arcs of length 1..n
  ...

Optimized Brute Force with Prefix Sums

Idea: Duplicate array to nums + nums, compute prefix sums, then for each start i (0…n-1) and length l (1…n), sum = prefix[i+l] - prefix[i].

def maxSubarraySumCircular_prefix(nums):
    n = len(nums)
    arr = nums + nums
    prefix = [0] * (2*n + 1)
    for i in range(2*n):
        prefix[i+1] = prefix[i] + arr[i]
    max_sum = float('-inf')
    for i in range(n):
        for l in range(1, n+1):
            max_sum = max(max_sum, prefix[i+l] - prefix[i])
    return max_sum

Complexity Proof:

• Time: O(n²) still, but each sum is O(1).
• Space: O(n) for prefix array.
  Visualization:

Linearized: [a0, a1, ..., a{n-1}, a0, a1, ..., a{n-1}]
Prefix: p0=0, p1=a0, p2=a0+a1, ...
Subarray (i,l) sum = p[i+l] - p[i]

Divide and Conquer

Idea: Break circle at an arbitrary point (e.g., index 0). The max subarray either doesn’t cross the break (standard divide-and-conquer for linear array) or crosses the break (wrap-around). The crossing case equals total sum minus minimum subarray sum. This leads to O(n log n) time.

def maxSubarraySumCircular_dc(nums):
    n = len(nums)
    # Helper for linear max subarray using divide and conquer
    def max_subarray(arr, l, r):
        if l == r: return arr[l]
        mid = (l + r) // 2
        left = max_subarray(arr, l, mid)
        right = max_subarray(arr, mid+1, r)
        # Cross sum
        left_sum = float('-inf')
        curr = 0
        for i in range(mid, l-1, -1):
            curr += arr[i]
            left_sum = max(left_sum, curr)
        right_sum = float('-inf')
        curr = 0
        for i in range(mid+1, r+1):
            curr += arr[i]
            right_sum = max(right_sum, curr)
        cross = left_sum + right_sum
        return max(left, right, cross)
    M_max = max_subarray(nums, 0, n-1)
    if M_max <= 0: return M_max
    # Minimum subarray sum (using similar divide and conquer or invert signs)
    # Alternatively, compute total and min separately.
    total = sum(nums)
    # Compute M_min using min-subarray version
    def min_subarray(arr, l, r):
        if l == r: return arr[l]
        mid = (l + r) // 2
        left = min_subarray(arr, l, mid)
        right = min_subarray(arr, mid+1, r)
        left_sum = float('inf')
        curr = 0
        for i in range(mid, l-1, -1):
            curr += arr[i]
            left_sum = min(left_sum, curr)
        right_sum = float('inf')
        curr = 0
        for i in range(mid+1, r+1):
            curr += arr[i]
            right_sum = min(right_sum, curr)
        cross = left_sum + right_sum
        return min(left, right, cross)
    M_min = min_subarray(nums, 0, n-1)
    return max(M_max, total - M_min)

Complexity Proof:

• Time: O(n log n) from recursion depth log n and linear cross computations.
• Space: O(log n) recursion stack.
  Visualization:

Split array into left and right halves.
Max subarray lies entirely in left, entirely in right, or crosses mid.
For circular, crossing the break (0 to n-1) is handled by total - min subarray.

Optimal Solution: Kadane’s Algorithm Variant

Idea: One-pass compute M_max, M_min, and total sum S. Then answer is max(M_max, S - M_min) if M_max > 0, else M_max.

def maxSubarraySumCircular(nums):
    total = 0
    max_ending_here = min_ending_here = 0
    max_so_far = float('-inf')
    min_so_far = float('inf')
    for x in nums:
        total += x
        # Kadane for max
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
        # Kadane for min
        min_ending_here = min(x, min_ending_here + x)
        min_so_far = min(min_so_far, min_ending_here)
    if max_so_far > 0:
        return max(max_so_far, total - min_so_far)
    else:
        return max_so_far

Complexity Proof:

• Time: O(n) single pass.
• Space: O(1) extra variables.
  Visualization:

Linear scan:
  max_ending_here: reset when adding x reduces sum below x itself.
  min_ending_here: reset when adding x increases sum above x itself.
At end, max_so_far is linear max, min_so_far is linear min.
Circular max = max(linear max, total - linear min) if linear max > 0.

Alternative: Doubled Array with Monotonic Queue

Idea: Duplicate array, compute prefix sums P of length 2n. For each ending index j (0…2n-1), find starting index i in [j-n+1, j] that minimizes P[i] to maximize P[j] - P[i]. Use a deque to maintain candidates in sliding window.

from collections import deque
def maxSubarraySumCircular_deque(nums):
    n = len(nums)
    arr = nums + nums
    prefix = [0] * (2*n + 1)
    for i in range(2*n):
        prefix[i+1] = prefix[i] + arr[i]
    deque_idx = deque()
    max_sum = float('-inf')
    for j in range(1, 2*n+1):
        # Remove indices outside window [j-n, j-1]
        while deque_idx and deque_idx[0] < j - n:
            deque_idx.popleft()
        # Current candidate: prefix[j] - prefix[deque_idx[0]]
        if deque_idx:
            max_sum = max(max_sum, prefix[j] - prefix[deque_idx[0]])
        # Maintain increasing order of prefix[i]
        while deque_idx and prefix[deque_idx[-1]] >= prefix[j]:
            deque_idx.pop()
        deque_idx.append(j)
    return max_sum

Complexity Proof:

• Time: O(n) – each index pushed/popped once.
• Space: O(n) for deque and prefix.
  Visualization:

Prefix: [p0, p1, ..., p{2n}]
Window of size n: for each j, find min p[i] in window j-n ≤ i ≤ j-1.
Maximize p[j] - p[i].
Deque stores increasing p[i] indices.

---

4. Code Deep Dive

Line-by-Line Annotations (Optimal Solution)

def maxSubarraySumCircular(nums):
    # total: cumulative sum of entire array for wrap-around computation.
    total = 0
    
    # max_ending_here: maximum sum of subarrays ending at current position.
    # max_so_far: overall maximum subarray sum found so far.
    # Initialize to -∞ to handle negative numbers.
    max_ending_here = 0
    max_so_far = float('-inf')
    
    # min_ending_here: minimum sum of subarrays ending at current position.
    # min_so_far: overall minimum subarray sum found so far.
    # Initialize to +∞ to ensure first comparison updates correctly.
    min_ending_here = 0
    min_so_far = float('inf')
    
    # Iterate through each element x in nums.
    for x in nums:
        # Update total sum of the array.
        total += x
        
        # Kadane's for maximum: either start a new subarray at x,
        # or extend the previous best subarray ending at previous position.
        max_ending_here = max(x, max_ending_here + x)
        # Update global maximum if current ending subarray is better.
        max_so_far = max(max_so_far, max_ending_here)
        
        # Kadane's for minimum: either start a new min subarray at x,
        # or extend the previous min subarray.
        min_ending_here = min(x, min_ending_here + x)
        # Update global minimum.
        min_so_far = min(min_so_far, min_ending_here)
    
    # After loop, max_so_far holds linear maximum subarray sum (M_max).
    # min_so_far holds linear minimum subarray sum (M_min).
    
    # Decision logic:
    # If M_max > 0, consider both linear and wrap-around cases.
    # Wrap-around sum = total - M_min.
    # If M_max <= 0, all numbers are non-positive, so wrap-around sum is 0 (invalid).
    # Thus return M_max (which is the largest single element or zero if present).
    if max_so_far > 0:
        return max(max_so_far, total - min_so_far)
    else:
        return max_so_far

Edge Case Handling

• Example 1 ([1,-2,3,-2]):
  max_so_far becomes 3 (subarray [3]), min_so_far = -2, total = 0. Since max_so_far>0, compute max(3, 0 - (-2)) = max(3,2)=3. Correct.

• Example 2 ([5,-3,5]):
  max_so_far = 7 (linear [5,-3,5]), min_so_far = -3, total = 7. max_so_far>0, so max(7, 7 - (-3)) = max(7,10)=10. Correct wrap-around [5,5].

• Example 3 ([-3,-2,-3]):
  max_so_far = -2 (largest single), min_so_far = -8, total = -8. max_so_far not >0, return -2. Correct.

• All negatives ([-1,-2,-3]):
  max_so_far = -1, min_so_far = -6, total = -6. Since max_so_far ≤ 0, return -1. Avoids invalid wrap-around 0.

• All positives ([1,2,3]):
  max_so_far = 6, min_so_far = 1, total = 6. max_so_far>0, max(6, 6-1)=6. Correct.

• Single element ([5]):
  max_so_far = 5, min_so_far = 5, total = 5. max_so_far>0, max(5, 5-5)=5. Correct.

• Zeros and negatives ([0,-1,0]):
  max_so_far = 0, min_so_far = -1, total = -1. max_so_far not >0? Actually 0 is not >0, so returns 0. Valid.

---

5. Complexity War Room

Hardware-Aware Analysis

• n ≤ 30,000: One-pass O(n) algorithm performs ~30k operations, trivial for modern CPUs (< 0.1 ms).
• Memory: Input ~120 KB (4-byte ints). Variables use < 100 bytes, fitting in L1 cache (typically 32-64 KB). Excellent cache locality.
• Branch Prediction: Loop has predictable branches (compare and update). Unlikely to cause pipeline stalls.
• Integer Operations: Sums stay within 32-bit range; no overflow checks needed.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(1)	9/10	❌ Fails large n
Prefix Sum Brute	O(n²)	O(n)	8/10	❌ Still O(n²)
Divide & Conquer	O(n log n)	O(log n)	6/10	⚠️ Acceptable but suboptimal
Kadane Variant (Optimal)	O(n)	O(1)	9/10	✅ Highly Recommended
Doubled Array + Deque	O(n)	O(n)	5/10	⚠️ More complex, but valid

---

6. Pro Mode Extras

Variants Section

1. Maximum Sum Circular Subarray with Length ≤ k
   Use monotonic queue on doubled array with window size k. Time O(n), space O(n).

2. Minimum Sum Circular Subarray
   Symmetric: min(M_min, S - M_max) with handling for all-positive arrays (where S - M_max = 0 invalid).

3. Maximum Sum Circular Subarray with One Deletion (LeetCode 1186 – Circular Version)
   Extend dynamic programming: track best with and without deletion, considering wrap-around via total minus minimum subarray with one deletion.

4. Maximum Sum Circular Subarray with Exactly k Elements
   Fixed-length sliding window on doubled array: compute prefix sums, then for each ending index j, sum = prefix[j] - prefix[j-k]. O(n).

5. Maximum Sum of Two Non-Overlapping Circular Subarrays
   Complex DP: partition circle into two arcs; similar to linear case but with wrap-around possibilities.

Interview Cheat Sheet

• First Sentence: “This is a circular version of Kadane’s problem. The key insight is that the maximum circular subarray is either the standard maximum subarray (no wrap) or the total sum minus the minimum subarray (wrap-around).”
• Edge Cases: “Always check if the linear maximum is positive before considering wrap-around, otherwise return the linear maximum (handles all-negative arrays).”
• Complexity: “One pass, O(n) time, O(1) space.”
• Testing: “Test with all negatives, all positives, mixed signs, and examples where wrap-around wins.”
• Follow-up: “If asked about length constraints, mention the monotonic queue technique on doubled array.”