Problem Description

You are given a circular integer array nums of length n. Your task is to find the maximum possible sum of a non-empty subarray within this circular array.

In a circular array, the elements wrap around - meaning the element after the last position connects back to the first position. Mathematically:

• The next element of nums[i] is nums[(i + 1) % n]
• The previous element of nums[i] is nums[(i - 1 + n) % n]

A key constraint is that each element can be included at most once in any subarray. This means if you choose a subarray that wraps around the circular array, you cannot reuse elements.

For example, if nums = [1, -2, 3, -2]:

• A regular subarray could be [3] with sum 3
• A circular subarray could be [3, -2, 1] (wrapping from index 2 to 0) with sum 2
• But you cannot have [1, -2, 3, -2, 1] as it would reuse the element at index 0

The challenge is to handle two scenarios:

1. The maximum sum subarray lies entirely within the array without wrapping (standard maximum subarray problem)
2. The maximum sum subarray wraps around the circular boundary

The solution cleverly handles both cases by:

• Finding the maximum subarray sum normally (Case 1)
• Finding the minimum subarray sum and subtracting it from the total sum (Case 2 - this gives us the wrapped-around maximum)

The answer is the maximum of these two cases.

Intuition

The key insight is recognizing that in a circular array, there are only two possible patterns for the maximum sum subarray:

Pattern 1: No Wrapping The maximum subarray is contained entirely within the array without using the circular property. This is just the classic Kadane's algorithm problem.

Pattern 2: Wrapping Around The maximum subarray wraps around from the end to the beginning of the array. Here's the clever observation: if the maximum subarray wraps around, then the elements NOT included in this subarray form a contiguous segment in the middle of the array.

Think about it this way: if we're taking elements from both ends (wrapping around), what we're leaving out is a continuous chunk in the middle. The sum of what we take equals total_sum - sum_of_middle_chunk.

To maximize what we take, we need to minimize what we leave out. Therefore, finding the maximum wrapped subarray sum is equivalent to finding the minimum subarray sum and subtracting it from the total.

For example, with nums = [5, -3, 5]:

• Total sum = 7
• Minimum subarray = [-3] with sum -3
• Maximum circular sum = 7 - (-3) = 10 (which corresponds to taking [5, 5])

The solution maintains prefix sums to efficiently calculate both:

• Maximum subarray sum: current_prefix_sum - minimum_prefix_sum_seen_so_far
• Minimum subarray sum: current_prefix_sum - maximum_prefix_sum_seen_so_far

By tracking these values in a single pass, we can find both the regular maximum (Pattern 1) and the wrapped maximum (Pattern 2), then return the larger of the two.

Learn more about Queue, Divide and Conquer, Dynamic Programming and Monotonic Queue patterns.

Solution Approach

The implementation uses a single-pass algorithm with prefix sums to find both the maximum regular subarray and the minimum subarray simultaneously.

Variables Maintained:

• pmi: Minimum prefix sum seen so far (initialized to 0)
• pmx: Maximum prefix sum seen so far (initialized to -inf)
• s: Current prefix sum (initialized to 0)
• smi: Minimum subarray sum found (initialized to inf)
• ans: Maximum subarray sum for non-wrapping case (initialized to -inf)

Algorithm Steps:

For each element x in the array:

1. Update prefix sum: s += x

   • This maintains the running sum from the start of the array

2. Update maximum subarray sum (non-wrapping): ans = max(ans, s - pmi)

   • The maximum subarray ending at current position = current prefix sum - minimum prefix sum before it
   • This handles Case 1 where the subarray doesn't wrap

3. Update minimum subarray sum: smi = min(smi, s - pmx)

   • The minimum subarray ending at current position = current prefix sum - maximum prefix sum before it
   • This is needed for Case 2 (wrapping scenario)

4. Update prefix sum bounds:

   • pmi = min(pmi, s) - Track minimum prefix sum for future calculations
   • pmx = max(pmx, s) - Track maximum prefix sum for future calculations

Final Answer: Return max(ans, s - smi) where:

• ans represents the maximum sum without wrapping (Case 1)
• s - smi represents the maximum sum with wrapping (Case 2)
  • s is the total sum of the array
  • smi is the minimum subarray sum
  • Their difference gives us the maximum circular subarray sum

Why This Works:

• By maintaining both minimum and maximum prefix sums, we can calculate the best subarray sum ending at any position
• The formula current_prefix - min_prefix gives maximum gain
• The formula current_prefix - max_prefix gives maximum loss (minimum subarray)
• Computing both in a single pass makes the algorithm O(n) time with O(1) space

Example Walkthrough

Let's walk through the algorithm with nums = [5, -3, 5]:

Initial State:

• pmi = 0 (minimum prefix sum seen)
• pmx = -inf (maximum prefix sum seen)
• s = 0 (current prefix sum)
• smi = inf (minimum subarray sum)
• ans = -inf (maximum non-wrapping subarray sum)

Step 1: Process nums[0] = 5

• Update prefix sum: s = 0 + 5 = 5
• Update max subarray: ans = max(-inf, 5 - 0) = 5
  • This represents subarray [5] with sum 5
• Update min subarray: smi = min(inf, 5 - (-inf)) = inf (remains inf)
• Update prefix bounds:
  • pmi = min(0, 5) = 0
  • pmx = max(-inf, 5) = 5

Step 2: Process nums[1] = -3

• Update prefix sum: s = 5 + (-3) = 2
• Update max subarray: ans = max(5, 2 - 0) = 5
  • 2 - 0 = 2 represents subarray [5, -3] with sum 2
  • We keep ans = 5 as it's larger
• Update min subarray: smi = min(inf, 2 - 5) = -3
  • 2 - 5 = -3 represents subarray [-3] with sum -3
• Update prefix bounds:
  • pmi = min(0, 2) = 0
  • pmx = max(5, 2) = 5

Step 3: Process nums[2] = 5

• Update prefix sum: s = 2 + 5 = 7
• Update max subarray: ans = max(5, 7 - 0) = 7
  • 7 - 0 = 7 represents subarray [5, -3, 5] with sum 7
• Update min subarray: smi = min(-3, 7 - 5) = -3
  • 7 - 5 = 2 represents subarray [-3, 5] with sum 2
  • We keep smi = -3 as it's smaller
• Update prefix bounds:
  • pmi = min(0, 7) = 0
  • pmx = max(5, 7) = 7

Final Calculation:

• Non-wrapping maximum: ans = 7 (subarray [5, -3, 5])
• Wrapping maximum: s - smi = 7 - (-3) = 10
  • This represents taking everything except the minimum subarray [-3]
  • Which means taking [5] from the end and [5] from the beginning
  • This is the circular subarray [5, 5] with sum 10

Result: max(7, 10) = 10

The algorithm correctly identifies that the maximum circular subarray sum is 10, achieved by the wrapping subarray [5, 5] that excludes the middle element -3.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once with a single for loop, performing constant-time operations (O(1)) for each element including addition, comparison, and variable updates.

The space complexity is O(1). The algorithm only uses a fixed number of variables (pmi, pmx, ans, s, smi) to track the minimum prefix sum, maximum prefix sum, maximum subarray sum, current sum, and minimum subarray sum respectively. These variables do not scale with the input size, resulting in constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Edge Case: All Negative Numbers

When all array elements are negative, the circular case calculation (total_sum - min_subarray_sum) would select an empty subarray, giving a sum of 0. However, the problem requires a non-empty subarray.

Example: nums = [-3, -2, -3]

• Maximum non-circular sum: -2
• Minimum subarray sum: -8 (entire array)
• Total sum: -8
• Circular case: -8 - (-8) = 0 (incorrect, as this represents an empty subarray)

Solution: Add a check to ensure we don't select the entire array as the minimum subarray:

# Check if minimum subarray is the entire array
if min_subarray_sum == current_sum:
    # All elements are included in min subarray, so circular case is empty
    return max_subarray_sum
else:
    return max(max_subarray_sum, current_sum - min_subarray_sum)

2. Initialization of max_prefix

Setting max_prefix = -float('inf') initially can cause issues because we're looking for the maximum prefix sum before the current element. Starting with negative infinity means the first element will always compute min_subarray_sum incorrectly.

Solution: Initialize max_prefix = 0 instead, representing an empty prefix:

max_prefix = 0  # Start with empty prefix, not -infinity

3. Misunderstanding Variable Updates Order

Updating min_prefix and max_prefix before calculating the subarray sums would include the current element's contribution in both the prefix and the subarray calculation, leading to incorrect results.

Incorrect order:

min_prefix = min(min_prefix, current_sum)  # Wrong: Updated too early
max_subarray_sum = max(max_subarray_sum, current_sum - min_prefix)

Correct order:

max_subarray_sum = max(max_subarray_sum, current_sum - min_prefix)
min_prefix = min(min_prefix, current_sum)  # Update after using it

4. Single Element Array

With arrays of length 1, the circular and non-circular cases are identical, but the minimum subarray calculation might behave unexpectedly if max_prefix starts at negative infinity.

Solution: Either handle single-element arrays separately or ensure proper initialization:

if len(nums) == 1:
    return nums[0]