LeetCode 152: Maximum Product Subarray ·

基本資料
#

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

學習脈絡
#

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

筆記中提到的相關提醒
#

1. Explain why LC 152 needs both cur_max and cur_min.

當天筆記摘錄
#

Problem 1 - LC 152 Maximum Product Subarray
#

Status: Good enough.
Pattern: Rolling DP with max/min state.

Why DP Fits
#

Product behaves differently from sum because a negative number can flip:

a very small negative product into the new maximum
a previous maximum into the new minimum

So one rolling state is not enough.

State
#

cur_max = maximum product of a subarray ending at current index
cur_min = minimum product of a subarray ending at current index

Important nuance:

"max" and "min" are value-based, not sign-based labels

Base Case
#

cur_max = cur_min = nums[0]
answer = nums[0]

Transition
#

For current number x, compute from:

x
previous cur_max * x
previous cur_min * x

So:

new_max = max(x, cur_max * x, cur_min * x)
new_min = min(x, cur_max * x, cur_min * x)

Then:

cur_max = new_max
cur_min = new_min
answer = max(answer, cur_max)

Complexity
#

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

Common Mistakes
#

tracking only one running product
forgetting that the DP boundary is “ending at i”
returning the final cur_max instead of a global answer

Interview-Ready Explanation
#

I track both the maximum and minimum product ending at each index, because multiplying by a negative can swap their roles. At each number, I either start a new subarray or extend the previous max/min product. I keep a separate global answer because the best subarray may end before the last index.

正確解法
#

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

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_here = min_here = ans = nums[0]

        for x in nums[1:]:
            a = x * max_here
            b = x * min_here
            max_here = max(x, a, b)
            min_here = min(x, a, b)
            ans = max(ans, max_here)

        return ans