NeetCode #777LC-918MediumGreedyNC 250
← Back to All Problems#777 · #918 · Maximum Sum Circular Subarray(环形子数组的最大和)
📌 Problem Statement & Constraints
Given a circular integer array
nums, return the maximum possible sum of a non-empty subarray of the circular array. Constraints: 1 <= nums.length <= 3 * 10^4, -3 * 10^4 <= nums[i] <= 3 * 10^4.💡 Core Algorithmic Approaches
- A maximum subarray is either a normal (non-wrapping) subarray or wraps around the ends.
- The non-wrapping case is standard Kadane's maximum.
- A wrapping subarray is the total sum minus a non-wrapping minimum subarray, i.e.
total - minSubarray. - If every element is negative, the wrapping candidate would be the empty subarray (sum 0), which is not allowed, so return the plain maximum in that case.
💻 Benchmark Python3 Implementation
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
cur_max = cur_min = 0
best_max = best_min = nums[0]
for x in nums:
total += x
cur_max = max(cur_max + x, x)
best_max = max(best_max, cur_max)
cur_min = min(cur_min + x, x)
best_min = min(best_min, cur_min)
if best_max < 0:
return best_max # all negative -> no wrapping
return max(best_max, total - best_min)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass tracking both Kadane variants.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Returning
total - best_minunconditionally: when all values are negative this yields 0, but the subarray must be non-empty; guard withbest_max < 0. - Forgetting the non-wrapping candidate: the answer is the maximum of the two cases.
- Computing the minimum subarray over the whole array with a different loop bound: both Kadanes run over the same pass.
- Handling a single-element array:
best_maxequals that element and the guard returns it correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.