最長單調遞增子序列 (LIS) O(n²) 動態規劃完整解析與 Java 實現

問題定義

給定長度為 n 的數列，求其最長嚴格遞增子序列的長度與具體序列。要求時間複雜度 O(n²)。

動態規劃狀態設計

• sub_len[i]：以第 i 個元素為起點（或結尾）的最長遞增子序列長度。
• sub_index[i]：該最優序列中緊接在第 i 元素之後的元素下標（用於路徑重構）。

本解法採用逆向 DP：從右向左計算，sub_len[i] 表示從 i 到 n 的最長遞增序列長度。

狀態轉移方程

sub_len[i] = 1 + max{ sub_len[j] | j > i 且 nums[i] < nums[j] }
sub_index[i] = argmax_j 的 j（若無則為 0）

演算法流程

1. 初始化：sub_len[i] = 1，sub_index[i] = 0。
2. 外層迴圈 i 從 n-1 遞減至 1。
   內層迴圈 j 從 i+1 至 n，尋找滿足 nums[i] < nums[j] 且 sub_len[j] 最大的 j。
3. 更新 sub_len[i] 與 sub_index[i]。
4. 掃描全域最大 sub_len[i]，得最長長度 max 與起點 p。
5. 沿 sub_index 鏈輸出序列。

完整 Java 代碼

import java.util.Scanner;

public class LIS_O_n2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] nums = new int[n + 1];
            int[] sub_len = new int[n + 1];
            int[] sub_index = new int[n + 1];

            for (int i = 1; i <= n; ++i) {
                nums[i] = sc.nextInt();
                sub_len[i] = 1;
                sub_index[i] = 0;
            }

            for (int i = n - 1; i >= 1; --i) {
                int maxLen = 0, pos = 0;
                for (int j = i + 1; j <= n; ++j) {
                    if (nums[i] < nums[j] && sub_len[j] > maxLen) {
                        maxLen = sub_len[j];
                        pos = j;
                    }
                }
                if (pos != 0) {
                    sub_len[i] = sub_len[pos] + 1;
                    sub_index[i] = pos;
                }
            }

            int max = 0, start = 0;
            for (int i = 1; i <= n; ++i) {
                if (sub_len[i] > max) {
                    max = sub_len[i];
                    start = i;
                }
            }

            System.out.println("最長長度：" + max);
            System.out.print("最長遞增序列：");
            while (start != 0) {
                System.out.print(nums[start] + " ");
                start = sub_index[start];
            }
            System.out.println();
        }
        sc.close();
    }
}

複雜度分析

• 時間：O(n²)，雙層迴圈各 n。
• 空間：O(n)，三個輔助陣列。

延伸：O(n log n) 做法簡介

維護一個 tail 陣列，tail[len] 存儲長度為 len 的遞增子序列的最小結尾值。對每個 x 二分查找在 tail 中的插入位置並更新，最終 tail 的有效長度即為 LIS 長度。若需輸出具體序列，需額外記錄前驅指標與位置資訊，實現稍繁雜但對大數據量 (n > 10⁵) 必不可少。