最長不下降子序列詳解

一、什麼是最長不下降子序列

最長不下降子序列（Longest Increasing Subsequence，簡稱LIS）是指在一個序列中，找出一個最長的子序列滿足單調遞增。其中的單調遞增是指數列中後一個數大於前一個數的情況。比如序列[3,1,4,1,5,9,2,6,5,3,5,8,9,7]的最長不下降子序列是[1,2,3,5,8,9]。

二、最長不下降子序列的求解方法

我們介紹兩種方法：動態規劃和二分查找法。

1. 動態規劃法

動態規劃的實現是通過維護一個計數數組dp，用來記錄以每個元素為結尾的子序列中最長的LIS長度。我們先初始化dp數組為1，因為每個單獨的元素的LIS都是1。

int lengthOfLIS_dp(int* nums, int numsSize) {
    if(numsSize <= 1) return numsSize;

    int dp[numsSize];
    for(int i=0; i<numsSize; i++) dp[i] = 1;

    int maxLen = 1;
    for(int i=1; i<numsSize; i++) {
        for(int j=0; j<i; j++) {
            if(nums[j] maxLen) ? dp[i] : maxLen;
    }

    return maxLen;
}

該演算法的時間複雜度是O(n^2)，空間複雜度是O(n)。

2. 二分查找法

該方法需要維護一個數組tails，其中tails[i]保存長度為i+1的LIS的最小末尾元素。由於tails長度是不斷增加的，因此我們需要一個變數size來維護tails的當前有效長度。

每次遍曆數組nums，對於每個元素num，我們在tails中尋找第一個大於等於num的位置index，將tails[index]更新為num，如果index等於size，則表明新增了一條長度為size+1的LIS，需要將size加1。

int lengthOfLIS_binarySearch(int* nums, int numsSize) {
    int tails[numsSize];
    int size = 0;
    for(int i=0; i<numsSize; i++) {
        int left = 0, right = size;
        while(left < right) {
            int mid = (left+right)/2;
            if(tails[mid] < nums[i]) left = mid+1;
            else right = mid;
        }
        tails[left] = nums[i];
        if(left == size) size++;
    }

    return size;
}

該演算法的時間複雜度是O(nlogn)，空間複雜度是O(n)。

三、最長不下降子序列的實際應用

最長不下降子序列在實際應用中有很多使用場景。這裡以紙牌遊戲為例，介紹一下如何將LIS演算法應用到遊戲中。

現在有一組撲克牌，每張牌都有一個權重weight，我們將這些牌分為兩部分，分別排列成兩個序列a和b。每次可以從a或b的頂部取走一張牌，並將該牌放置在一個額外的序列c的頂部。請問當序列a和b遍歷完畢後，序列c的最長不下降子序列的長度是多少？

這個問題可以很自然地轉化為求解在序列a和b中取出若干個數後，它們的最長不下降子序列的長度。我們將a和b的元素對應相加，得到一個新的序列，然後求新序列的最長不下降子序列長度即可解決問題。

int max(int a, int b) {
    return (a>b) ? a : b;
}

int lengthOfLIS_game(int* a, int aSize, int* b, int bSize) {
    int c[aSize];
    for(int i=0; i<aSize; i++) c[i] = a[i]+b[i];

    int dp[aSize];
    for(int i=0; i<aSize; i++) dp[i] = 1;

    int maxLen = 1;
    for(int i=1; i<aSize; i++) {
        for(int j=0; j<i; j++) {
            if(c[j] < c[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }

    return maxLen;
}

四、結語

本文介紹了最長不下降子序列的定義、求解方法和實際應用。動態規劃和二分查找法都是常用的LIS求解方法，它們的時間和空間複雜度有所不同，選擇不同的演算法取決於具體應用場景。在遊戲開發中，LIS演算法可以被廣泛地應用，為遊戲增添了一份趣味和挑戰。