d242. 00481 - What Goes Up -- UVa481 | From: [106.1.117.161] | 發表日期 : 2024-10-26 13:53

1. 構造問題: 找出最長遞增子序列

2. 定義狀態: f(i) = 到 index i 為止的最長遞增子序列

3. 求解小規模的簡單問題: f(0) = 1

4. 狀態轉移方程式:

    f(i) = max( f(j) + 1 | nums[i] > nums[j])

    (如果 nums[i] > nums[j], 那麼 f(j) + 1 就是預備答案之一, 最後要找最大的)

5. 判斷複雜度: O(n^2)

 

可以透過「耐心排序」將複雜度降低到 O(nlogn), 同時節省空間