LeetCode 53: Maximum Subarray ·

基本資料
#

難易度: medium 第一次嘗試：2026-05-10 來源：Day 21 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

1. Explain LC 53 with the exact ending-here invariant and correct initialization.
1. Explain why LC 53 needs best separately from curr.
LC 53 Maximum Subarray: Pass.
1. Re-answer LC 53 once more later with no wording drift on the invariant.

當天筆記摘錄
#

Problem 1 - LC 53 Maximum Subarray
#

Status: Pass.
Pattern: 1D DP with rolling state / Kadane’s algorithm.

Correct State
#

curr = maximum subarray sum ending at the current index
best = maximum subarray sum seen so far

Why This State Fits
#

For any index i, the best subarray ending at i has only 2 possibilities:

start fresh at nums[i]
extend the best subarray ending at i - 1

That gives the recurrence:

curr = max(nums[i], curr + nums[i])
best = max(best, curr)

Initialization
#

curr = best = nums[0]

Why:

all-negative arrays are valid, so initializing to 0 would be wrong

Complexity
#

Time: O(n)
Space: O(1)

Common Mistakes
#

saying curr is just “current subarray sum” instead of the exact ending-here invariant
initializing to 0, which breaks all-negative arrays
returning curr instead of best

Interview-Ready Explanation
#

This is 1D DP with rolling state, also known as Kadane’s algorithm. I define curr as the maximum subarray sum ending at the current index, and best as the maximum subarray sum seen so far. For each element, the best subarray ending here either starts fresh at this element or extends the previous ending-here subarray, so curr = max(nums[i], curr + nums[i]). Then I update best = max(best, curr). I initialize both to nums[0] so all-negative arrays are handled correctly. The time complexity is O(n) and the space complexity is O(1).

Code
#

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr = best = nums[0]

        for i in range(1, len(nums)):
            curr = max(nums[i], curr + nums[i])
            best = max(best, curr)

        return best

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr = best = nums[0]
        for x in nums[1:]:
            curr = max(x, curr + x)
            best = max(best, curr)
        return best