最長遞增子序列（longest increasing subsequence, LIS）

給定一串數字，最長遞增子序列是其中最長的一個選取——保留它們原本由左而右的順序但允許有間隙——且其值嚴格遞增。對序列 3, 1, 4, 1, 5, 9, 2, 6，一個最長遞增子序列是 1, 4, 5, 9（或 1, 4, 5, 6），長度為 4。它出現在你想找出時間排序資料中最長的一段持續改善時、在接龍紙牌遊戲中、以及作為一個既有簡單動態規劃又有更俐落解法的乾淨練習。

簡單的動態規劃定義 dp[i] = 恰以索引 i 結尾的最長遞增子序列長度。「以 i 結尾」這句話是關鍵的狀態設計手法：它固定了最後一個元素，使未來得以計算。轉移回顧每個值較小的較早索引 j < i，並延伸其中最佳的子序列：dp[i] = 1 + 在 j < i 且 a[j] < a[i] 中取 dp[j] 的最大值，若不存在更小的較早元素則就是 1。答案是所有 i 中最大的 dp[i]（最長遞增子序列不一定以最後一個元素結尾）。對 n 個元素，每個做 O(n) 掃描，這是 O(n^2) 時間與 O(n) 空間，而為每個 i 存下獲勝的前驅 j，就能回溯出真正的子序列。

有兩件事值得標出。第一，「遞增」通常指嚴格遞增；若允許相等值（非遞減），比較就從 a[j] < a[i] 改成 a[j] <= a[i]，所以務必確認問題要的是哪種。第二，O(n^2) 版本是基礎的那個，但有一個著名的更快方法，藉由二分搜尋維護「每個長度的遞增子序列所能達到的最小可能尾值」，達到 O(n log n)——那個最佳化屬於進階工具箱，但知道二次的動態規劃並非定論是好的。一個微妙的正確性要點：dp[i] 之所以正確地數出以 i 結尾的最佳值，是因為依最佳子結構，一個以 i 結尾的最佳遞增子序列把最後一個元素移除後，正是一個以前一個被選索引結尾的最佳遞增子序列。