題目

給你一個整數陣列 nums ，找到其中最長嚴格遞增子序列的長度，

子序列是由陣列派生而來的序列，洗掉（或不洗掉）陣列中的元素而不改變其余元素的順序，例如，[3,6,2,7] 是陣列 [0,3,1,6,2,2,7] 的子序列，

示例 1：

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 ，

示例 2：

輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：

輸入：nums = [7,7,7,7,7,7,7]
輸出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

進階：

你可以設計時間復雜度為 O(n2) 的解決方案嗎？
你能將演算法的時間復雜度降低到 O(n log(n)) 嗎?

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

解題思路

考慮使用動態規劃，從第一位開始，分別記錄位置 i 之前的最長遞增子序列，在其后 j 位置上，如果數值比 i 位數值要大，則 j 位置的元素可以接在 i 后方，子序列長度為 i 的子序列長度加一，代碼如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        int max=1;//初始最長遞增子序列為1
        vector<int> dp(nums.size(),1);//儲存各位及其之前的子序列長度
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]&&dp[i]<dp[j]+1)
                    dp[i]=dp[j]+1;
            }
            if(dp[i]>max)
                max=dp[i];
        }
        return max;
    }
};

代碼執行效果一般

根據題目進階要求時間復雜度降低到 O(n log(n)) ，看題解學習更優解法

優化解法

官解提出使用貪心+二分查找的解法，內容如下：

考慮一個簡單的貪心，如果我們要使上升子序列盡可能的長，則我們需要讓序列上升得盡可能慢，因此我們希望每次在上升子序列最后加上的那個數盡可能的小，

基于上面的貪心思路，我們維護一個陣列 d[i]d[i] ，表示長度為 ii 的最長上升子序列的末尾元素的最小值，用 \textit{len}len 記錄目前最長上升子序列的長度，起始時 lenlen 為 11，d[1] = \textit{nums}[0]d[1]=nums[0]，

同時我們可以注意到 d[i]d[i] 是關于 ii 單調遞增的，因為如果 d[j] \geq d[i]d[j]≥d[i] 且 j < ij<i，我們考慮從長度為 ii 的最長上升子序列的末尾洗掉 i-ji?j 個元素，那么這個序列長度變為 jj ，且第 jj 個元素 xx（末尾元素）必然小于 d[i]d[i]，也就小于 d[j]d[j]，那么我們就找到了一個長度為 jj 的最長上升子序列，并且末尾元素比 d[j]d[j] 小，從而產生了矛盾，因此陣列 dd 的單調性得證，

我們依次遍歷陣列 \textit{nums}nums 中的每個元素，并更新陣列 dd 和 lenlen 的值，如果 \textit{nums}[i] > d[\textit{len}]nums[i]>d[len] 則更新 len = len + 1len=len+1，否則在 d[1 \ldots len]d[1…len]中找滿足 d[i - 1] < \textit{nums}[j] < d[i]d[i?1]<nums[j]<d[i] 的下標 ii，并更新 d[i] = \textit{nums}[j]d[i]=nums[j]，

根據 dd 陣列的單調性，我們可以使用二分查找尋找下標 ii，優化時間復雜度，

最后整個演算法流程為：

設當前已求出的最長上升子序列的長度為 \textit{len}len（初始時為 11），從前往后遍歷陣列 \textit{nums}nums，在遍歷到 \textit{nums}[i]nums[i] 時：

如果 \textit{nums}[i] > d[\textit{len}]nums[i]>d[len] ，則直接加入到 dd 陣列末尾，并更新 \textit{len} = \textit{len} + 1len=len+1；

否則，在 dd 陣列中二分查找，找到第一個比 \textit{nums}[i]nums[i] 小的數 d[k]d[k] ，并更新 d[k + 1] = \textit{nums}[i]d[k+1]=nums[i]，

以輸入序列 [0, 8, 4, 12, 2][0,8,4,12,2] 為例：

第一步插入 00，d = [0]d=[0]；

第二步插入 88，d = [0, 8]d=[0,8]；

第三步插入 44，d = [0, 4]d=[0,4]；

第四步插入 1212，d = [0, 4, 12]d=[0,4,12]；

第五步插入 22，d = [0, 2, 12]d=[0,2,12]，

最終得到最大遞增子序列長度為 33，

作者：LeetCode-Solution

鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/

來源：力扣（LeetCode）

著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

代碼如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        int len=1;//記錄子序列
        vector<int> d(nums.size()+1,0);//長度進一位方便計算
        d[len]=nums[0];
        for(int i=1;i<nums.size();i++){
            if(nums[i]>d[len])
                d[++len]=nums[i];
            else{
                int l=1,r=len,pos=0;
                int mid=(l+r)/2;
                while (l <= r) {
                    int mid = (l + r)/2;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }  
        }
        return len;
    }
};

代碼執行效果較好