💬 Discord
Sign In
NeetCode #775LC-53MediumGreedyBlind 75NC 150NC 250
← Back to All Problems

#775 · #53 · Maximum Subarray(最大子数组和)

📌 Problem Statement & Constraints

Given an integer array nums, find the contiguous subarray (containing at least one number) with the largest sum and return that sum. Constraints: 1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Kadane's algorithm: keep a running sum cur of the best subarray ending at the current index.
  2. At each element, either extend the previous subarray (cur + x) or restart from x; take the larger.
  3. Track the maximum value cur ever reaches as the answer.
  4. The restart option is what handles negative prefixes: any prefix that drags the sum down is simply dropped.

💻 Benchmark Python3 Implementation

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best = cur = nums[0]
        for x in nums[1:]:
            cur = max(x, cur + x)      # extend or restart here
            best = max(best, cur)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single left-to-right pass.
💾 Space Complexity
O(1): two running scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Initialising best = 0: for an all-negative array such as [-3, -1, -2] the answer is -1, but a zero initialisation would return 0. Initialise from nums[0].
  • Resetting cur to 0 whenever it goes negative: that also breaks all-negative input; use cur = max(x, cur + x) instead of an explicit reset.
  • Returning the subarray rather than the sum: this problem asks only for the sum.
  • Using the divide-and-conquer solution: it is O(n log n) and far more code when the linear scan already works.