1. 最長上升子序列（LIS）

1.1. 題目

想象你有一排數字，比如：3, 1, 2, 1, 8, 5, 6

你要從中挑出一些數字，這些數字要滿足兩個條件：

1. 你挑的數字的順序要和原來序列中的順序一致（不能打亂順序）

2. 你挑的數字要一個比一個大（嚴格遞增）

問：最多能挑出多少個這樣的數字？

比如上面這個例子：

• 可以挑 3, 8（但長度只有2）

• 可以挑 1, 2, 5, 6（長度是4）

• 也可以挑 1, 2, 8（長度是3）

最長的就是4，所以答案是4

1.2. 思路（動態規劃）

我們用一個數組dp來記錄：

• dp[i] 表示：以第i個數字結尾時，能組成的最長上升子序列的長度

比如對于序列 [3,1,2,1,8,5,6]：

1. 第一個數字3：只能選它自己，所以dp[0]=1

2. 第二個數字1：比3小，不能接在3后面，只能自己開頭，dp[1]=1

3. 第三個數字2：

   • 可以接在1后面（1<2），所以長度=dp[1]+1=2

   • 不能接在3后面（3>2）

   • 所以dp[2]=2

4. 第四個數字1：

   • 比前面的3,1,2都小，只能自己開頭

   • dp[3]=1

5. 第五個數字8：

   • 可以接在3后面（3<8），長度=dp[0]+1=2

   • 可以接在1后面（1<8），長度=dp[1]+1=2

   • 可以接在2后面（2<8），長度=dp[2]+1=3

   • 可以接在前面的1后面（1<8），長度=dp[3]+1=2

   • 最大的是3，所以dp[4]=3

6. 繼續計算最后兩個數字...最終dp = [1,1,2,1,3,3,4]

7. 最大值是4，所以答案是4

1.3. 完整代碼（動態規劃）

n = int(input())  # 先讀取數字的個數
nums = list(map(int, input().split()))  # 讀取數字序列# 初始化dp數組，每個數字自己就是一個長度為1的子序列
dp = [1] * n  # 從第二個數字開始檢查（因為第一個數字的dp值肯定是1）
for i in range(1, n):# 看看前面所有數字for j in range(i):# 如果前面的數字比當前數字小，就可以接在后面if nums[j] < nums[i]:# 更新dp[i]，選擇更大的值dp[i] = max(dp[i], dp[j] + 1)# 相當于說："如果接在這個數字后面，會不會讓序列更長&#