# 最長遞增子序列 (LIS)
問題描述 : 給定一個數值陣列，找到一個子序列，該子序列中的元素必須嚴格遞增，並且使這個子序列的長度盡可能長，只要找到長度即可，(序列的意思表示可以不連續)。

例子 : 0, 1, -2, -1, 3, 5
最長的遞增子序列為 0, 1, 3, 5 (-2, -1, 3, 5)，長度為 4

### 第一種方法 : 暴力法
方法 : 從長度1到n，試著枚舉所有的子序列，接著判斷是否符合嚴格遞增，如果符合那就更新最長的長度。

時間複雜度 : 2^n，因為每個元素可以拿或不拿，這個方法的時間複雜度太高不太實際。

### 第二種方法 : 動態規劃
方法 : 我們維護一個陣列 dp，dp[i] 表示以第i個元素為結尾的最長遞增子序列長度，因此我們可以得到狀態轉移方程 : dp[i] = max(dp[0...i-1])+1。

時間複雜度 : n^2，因為對於每個元素都需要從頭開始找，該元素如果比在它前面的元素還要大就可以套用上述的轉移方程。

程式碼 :

int ans = 0, dp[n] = {1};
for(int i=1; i<n; i++){
    for(int j=0; j<i; j++){
        if(num[i] > num[j])
            dp[i] = max(dp[i], dp[j]);
    }
    dp[i]++;
    ans = max(ans, dp[i]);
}

### 第三種方法 : 動態規劃+二分搜尋法
方法 : 維護一個額外的陣列 dp，然後遍歷整個數值陣列，如果當前的元素大於dp中所有的元素，那就直接將該元素添加至dp的尾端，否則就在dp中找到大於該元素的最小值，並且替換它，最後dp的長度即為最長遞增子序列的長度。

用上面的例子做解釋 : 0, 1, -2, -1, 3, 5

遇到 0 : dp 為空 => 放進去 => dp : 0
遇到 1 : dp 的最大值為 0 => 添加至dp的尾端 => dp : 0, 1
遇到 -2 : dp 的 0 大於 -2 => 所以替換成 -2 => dp : -2, 1
遇到 -1 : dp 的 1 大於 -1 => 所以替換成 -1 => dp : -2, -1
遇到 3 : dp 的最大值為 -1 => 添加至dp的尾端 => dp : -2, -1, 3
遇到 5 : dp 的最大值為 3 => 添加至dp的尾端 => dp : -2, -1, 3, 5
最後 dp 的長度為 4 即為最長遞增子序列的長度。

這方法看起來很棒，那為甚麼是對的?
我數學不好，寫不出嚴格的證明QQ，只能直觀的思考 : 首先貪心的想一下，為了讓長度更長，所以前面的值越小越好，因此替換值就表示這個值比之前的值有更高的機率可以形成更長的子序列，因此我們才做這樣的替換。

時間複雜度 : n*log(n)，因為要遍歷整個陣列，不過維護的陣列 dp 因為是有序的，所以可以使用二分搜尋法。

程式碼 :

int dp[n] = {num[0]}, p = 1; // p 表示最長遞增子序列的長度
for(int i=1; i<n; i++){
    if(num[i] > dp[p-1]){
        dp[p] = num[i];
        p++;
    }
    else{
        int l = 0, r = p-1, m = 0;
        while(r - l > 1){
            m = l + (r - l) / 2;
            if(dp[m] >= num[i])
                r = m;
            else
                l = m;
        }
        dp[r] = num[i];
    }
}
cout << p << endl;