思路：

• 先找最长递增子序列长度
• 再根据长度逆向得到序列（逆向的原因是字典序更小，若是小值跑到后面去的情况，同样长度大值跑后面只会增加子序列长度）

要找到最长的递增子序列长度，常用方法是动态规划，dp[i]表示到元素i结尾时，最长的子序列的长度，初始化全部为1。

方法一：暴力动态规划（超时）

具体做法：

遍历两层，前面的指针i记录元素，后面指针j比较与前面的值，若是前面大，理论上dp[i]需要加上1，但是需要用dp[i] < dp[j] + 1判断是否是需要这个j，若是还有更大的就不需要这个j。但是因为两层遍历，时间复杂度很高，会超时。

class Solution {
public:
    vector<int> LIS(vector<int>& arr) {
        vector<int> dp(arr.size(), 1); //设置数组长度大小的动态规划辅助数组
        int max = 0;
        for(int i = 1; i < arr.size(); i++){
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1; //i点比j点大，理论上dp要加1
                    //但是可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                    max = max > dp[i] ? max : dp[i]; //找到最大长度
                }
            }
        }
        vector<int> res(max);
        for(int i = dp.size() - 1, j = max; j > 0; i--){ //逆向找
            if(dp[i] == j){ //该点的长度恰好等于res的第j位，即找到了
                j--;
                res[j] = arr[i];
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，两层for循环
• 空间复杂度：$O\left(n\right)O(n)$O(n)，辅助数组dp的大小

方法二：二分法动态规划

具体做法：

设置两个辅助数组：dp与len,len起着方法一dp的作用，dp[i]记录以i结尾的最大递增字符字串。dp记录的则是以i结尾的最大递增字符串，对于每次循环，从后找到比它大的数字，加入dp，若出现第一个不必dp中最后一位数大的，则需要使用二分查找，对剩下部分找第一个大于dp中最后一位的，再将其加入。由此，方法一中的第二个循环就变了一个lgn的二分查找。

class Solution {
public:
    int biSearch(int x, vector<int>& dp){  //二分查找函数
        int left = 0, right = dp.size(), mid;
        while(left <= right){
            mid = (right + left) / 2;
            if(dp[mid] >= x) 
                right = mid - 1;
            else 
                left = mid + 1;
        }
        return left;
    }
    vector<int> LIS(vector<int>& arr) {
        if(arr.size() == 0){  //处理特殊情况
            vector<int> res;
            return res;
        }
        vector<int> len; //设置数组长度大小的动态规划辅助数组
        vector<int> dp;//用于二分划分的辅助数组
        dp.push_back(arr[0]);
        len.push_back(1);
        for(int i = 1; i < arr.size(); i++){
			  if(arr[i] > dp[dp.size() - 1]) {  
                  dp.push_back(arr[i]);
                  len.push_back(dp.size());
              }
			  else{
				  int t = biSearch(arr[i], dp); //二分查找，找到第一个大于arr[i]的dp位置
				  dp[t] = arr[i];
                  len.push_back(t + 1);
			  }
		}
        int j = dp.size();
        vector<int> res(j);
        for(int i = len.size() - 1; j > 0; i--){ //逆向找
            if(len[i] == j){ //该点的长度恰好等于res的第j位，即找到了
                j--;
                res[j] = arr[i];
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，遍历一次，每次的二分查找为$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)
• 空间复杂度：$O\left(n\right)O(n)$O(n)，借助了辅助空间dp与len