⚡Flashcard Drill➔
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

  1. A maximum subarray is either a normal (non-wrapping) subarray or wraps around the ends.
  2. The non-wrapping case is standard Kadane's maximum.
  3. A wrapping subarray is the total sum minus a non-wrapping minimum subarray, i.e. total - minSubarray.
  4. 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_min unconditionally: when all values are negative this yields 0, but the subarray must be non-empty; guard with best_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_max equals 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems