Problem Breakdown
We need to find the maximum sum of a non-empty subarray within a circular array A. A circular array implies that after index n-1, we wrap around back to index 0. However, an element cannot be used twice (we can’t traverse more than one full circle).
- Inputs: An integer list
Awhere-30000 <= A[i] <= 30000and length is between1and30000. - Outputs: The maximum possible sum of a contiguous subarray (considering the wrap-around).
- Implicit Constraints:
- Subarrays must be non-empty. This means we cannot return 0 if all numbers are negative; we must pick at least one element.
- We can’t traverse more than once, so valid circular subarrays either stay within
[i...j]or wrap fromend[i..n-1] + [0..start[j]].
Intuition
A brute-force approach would iterate through every possible start and end index modulo the array length. This results in complexity, which is insufficient for an input size of 30,000 (targeting ~ operations). We need a linear solution.
We can leverage Kadane’s Algorithm, which finds the maximum subarray sum in . There are two types of valid subarrays:
- Non-Circular: A standard contiguous segment within
A. This is solved by Kadane’s algorithm directly onA. - Circular: Wraps around from end to start. Mathematically, a circular subarray corresponds to the total sum of the array minus a non-circular “gap” (the minimum subarray). If we remove the smallest contiguous segment that doesn’t wrap, what remains is our maximum circular subarray.
Key Insight: Max Circular Sum = Total Array Sum - Min Subarray Sum.
However, there’s an edge case: if all numbers are negative, calculating Total - Min might result in 0 (implying we took nothing), which violates the non-empty constraint. In this scenario, Kadane’s algorithm on its own gives us the maximum single element (the least negative number).
Approach
- Calculate Standard Max Subarray: Run Kadane’s Algorithm to find
max_kadanefor a linear array traversal. - Calculate Total Sum: Compute the sum of all elements in
A. - Calculate Min Subarray: Modify Kadane’s logic (or negate values) to find the minimum contiguous subarray sum, stored as
min_kadane. - Handle Edge Case: If all numbers are negative,
max_kadanewill be less than zero. In this case, we cannot use the circular formula because it would imply an empty set (summing everything minus itself). We must returnmax_kadane. Otherwise, comparemax_kadaneand(total_sum - min_kadane), returning the larger value.
Complexity Analysis
- Time Complexity: where N is the length of array A. We traverse the list a constant number of times (once for max sum, once implicitly within total/min logic).
- Space Complexity: auxiliary space. We only store running sums and counters; no extra data structures are used proportional to input size.
Solution
class Solution:
def maxSubarraySumCircular(self, A):
"""
:type A: List[int]
:rtype: int
"""
# Kadane's algorithm for maximum non-circular subarray sum
current_max = 0
global_max = float('-inf')
total_sum = 0
min_current = 0
min_global = float('inf')
for num in A:
total_sum += num
# Max Kadane's logic
current_max += num
if current_max < 0:
current_max = 0
global_max = max(global_max, current_max)
# Min Subarray logic (Reverse of Kadane's)
min_current += num
if min_current > 0:
min_current = 0
min_global = min(min_global, min_current)
# Edge case handling for all-negative numbers.
# If max_kadane < 0, it implies every element is negative (or zero).
# In this scenario, total_sum == min_subarray_sum usually, leading to a circular sum of 0.
# But we need non-empty subarrays, so if the best linear scan was negative,
# that's our answer regardless of circular logic which might imply empty set.
if global_max < 0:
return global_max
# Otherwise compare standard max vs circular (total - min)
return max(global_max, total_sum - min_global)
Edge Cases Handled
- All Negative Numbers: If the input is
[-2, -3],global_maxwill be-2. The logic detects this viaif global_max < 0and returns-2instead of incorrectly returning0(which would imply an empty subarray). - Single Element Array: Works correctly whether positive or negative. If
[5], returns5. If[-3], returns-3. - Mixed Signs with Wrap-Around: For inputs like
[5, -3, 5](Example 2), the linear max is7([5,-3,5]) or just single elements? Wait, standard Kadane on[5, -3, 5]:- i=0: curr=5, global=5.
- i=1: curr=2, global=5.
- i=2: curr=7, global=7.
Wait, Example 2 output is
10. My manual trace of standard Kadane gave7(whole array). The circular logic calculatesTotal(7) - Min(-3) = 10. This correctly identifies the wrap-around[5] + [5].
- Zero Values: Handled naturally by initialization and accumulation. If a zero exists, it doesn’t break Kadane’s logic (sums remain same).