Java 實現 LIS 最長上升子序列算法：出操隊形問題完整解法

Java 實現 LIS 最長上升子序列算法：出操隊形問題完整解法

經典算法問題：給定序列求最長上升子序列 (LIS) 長度。本文講解 O(n²) 動態規劃核心邏輯，並關聯「出操隊形」實戰場景，提供完整 Java 實現代碼。

問題定義

序列 [2, 1, 3, 5] 的最長上升子序列為 [2, 3, 5] 或 [1, 3, 5]，長度 = 3。

LIS 動態規劃核心思想

1. 定義 dp[i] 為以 a[i] 結尾的最長上升子序列長度
2. 狀態轉移：dp[i] = max(dp[j]) + 1，其中 0 ≤ j < i 且 a[j] < a[i]
3. 若無滿足條件的 j，則 dp[i] = 1
4. 最終答案：max(dp[i])

Java 實現代碼

public class LIS {
    public static int[] computeLISLengths(int[] a) {
        int n = a.length;
        int[] dp = new int[n];
        dp[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int maxLen = 0;
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j] && dp[j] > maxLen) {
                    maxLen = dp[j];
                }
            }
            dp[i] = maxLen + 1;
        }
        return dp;  // dp[i] 存儲以 a[i] 結尾的 LIS 長度
    }
    
    public static int getLISLength(int[] a) {
        int[] dp = computeLISLengths(a);
        int max = 0;
        for (int len : dp) if (len > max) max = len;
        return max;
    }
    
    // 測試
    public static void main(String[] args) {
        int[] arr = {2, 1, 3, 5};
        System.out.println("LIS 長度: " + getLISLength(arr));  // 輸出 3
    }
}

出操隊形問題關聯

「出操隊形」常見變體：給定學生身高序列，調整最少學生位置使隊伍身高單調遞增/遞減。本質上等價於求 LIS，最少移動次數 = 總人數 - LIS 長度。

優化方向 (O(n log n))

維護一個 tails 數組，tails[len] 存儲長度為 len+1 的上升子序列的最小尾部值。遍歷序列，二分查找插入位置更新 tails，最終 tails 長度即 LIS 長度。適合 n > 10⁴ 的大數據場景。

總結

LIS 是動態規劃入門經典，O(n²) 代碼簡潔易懂，適合面試與中小規模數據；出操隊形等實戰問題本質同構，掌握核心狀態定義與轉移方程即可舉一反三。