LeetCode 300: Longest Increasing Subsequence ·

基本資料
#

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

學習脈絡
#

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

筆記中提到的相關提醒
#

1. Explain why LC 300 DP state must mean “ending at i”.

當天筆記摘錄
#

Problem 2 - LC 300 Longest Increasing Subsequence
#

Status: Good enough for both O(n^2) DP and O(n log n) follow-up.
Pattern: Sequence DP, plus greedy + binary search optimization.

O(n^2) DP
#

Why DP Fits
#

For each index i, the LIS ending at i depends on earlier indices j < i whose values are smaller than nums[i].

State
#

dp[i] = length of the longest increasing subsequence ending at index i

Base Case
#

dp[i] = 1 for every i

Reason:

each element alone is an increasing subsequence of length 1

Transition
#

for each j < i:
    if nums[j] < nums[i]:
        dp[i] = max(dp[i], dp[j] + 1)

Answer
#

max(dp)

Complexity
#

Time: O(n^2)
Space: O(n)

Common Mistakes
#

saying “choose index i as one of the elements” instead of “ending at i”
forgetting the answer is global max, not just dp[-1]

O(n log n) Follow-Up
#

Core Idea
#

Keep:

tails[len - 1] = the smallest possible tail value of an increasing subsequence of length len

Why smaller tail is better:

for the same subsequence length, a smaller tail gives more future extension options

Update Rule
#

For each number:

if it is larger than all tails, append it
otherwise replace the first tail >= num

Important Nuance
#

tails is not always the actual LIS sequence

But:

len(tails) is the correct LIS length

Complexity
#

Time: O(n log n)
Space: O(n)

Interview-Ready Explanation
#

The O(n^2) DP uses dp[i] as the LIS ending at i. The O(n log n)` follow-up keeps the smallest possible tail for each subsequence length and uses binary search to replace tails. A smaller tail is better because it leaves more room for future extension.

正確解法
#

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

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)