# 演算法介紹 - 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](https://hackmd.io/uWmlY0wpQ-iDoMuT4l66ig)
#### 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](https://leetcode.com/problems/longest-increasing-subsequence/)
zerojudge: [APCS飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608)
>[name=Peter Wang]
>[time=Mon, Nov 1, 2021 11:26 PM]