演算法介紹 - Longest Increasing Subsequence - by Peter Wang

tags: 演算法介紹 DP LIS

名詞定義	內容敘述
Sequence	「數列」:一串數字。「序列」:一串字元。
Subsequence	「子序列」。 sequence 之中，依照由左到右的順序，挑幾個數字出來，就是 subsequence 。其中 sub- 的意思是「附屬、次要」。
Increasing	「遞增」:數字不斷增加。
Longest Increasing Subsequence （ LIS ）	「最長遞增子序列」。所有子序列當中，遞增的、最長的子序列，可能有許多個。

Longest Increasing Subsequence: Dynamic Programming

O(n^2)演算法簡介：

紀錄每項數字為結尾的 LIS 。 online 演算法，一次讀取一個數字，窮舉先前每項數字為結尾的 LIS ，看看哪一種接得最長。

O(n^2)程式範例（以leetcode的LIS基本題為例）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=nums.size();
        int dp[len];
        fill(dp,dp+len,1);
        //dp[0]=1;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[j]+1,dp[i]);
                }
            }
        }
        int ans=-1;
        for(int i=0;i<len;i++){
            if(dp[i]>ans){
                ans=dp[i];
            }
        }
        return ans;
    }
};

O(nlogn)演算法簡介：

nlogn的解法重點在使用lower_bound其餘概念同上。
如需了解lower_bound，可點擊以下連結。
資料結構介紹 - Upper_bound & Lower_bound - by Peter Wang

O(nlogn)程式範例（以leetcode的LIS基本題為例）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=nums.size();
        vector <int> dp;
        dp.push_back(nums[0]);
        for(int i=1;i<len;i++){
            if(nums[i]>dp.back()){
                dp.push_back(nums[i]);
            }
            else{
                *lower_bound(dp.begin(),dp.end(),nums[i])=nums[i];
            }
        }
        return dp.size();
    }
};

LIS題單

Leetcode: 300. Longest Increasing Subsequence
zerojudge: APCS飛黃騰達

Peter Wang
Mon, Nov 1, 2021 11:26 PM