题意：
        给定一个数组，求严格上升子序列的最大长度。

方法一：
动态规划(超时)

思路：
        动态规划。
        dp[ i ]表示以a[ i ]为结尾的严格上升子序列的长度。
        针对每个a[ i ]，遍历 i 前面的值a[ j ] :
            
        如果 a[ j ] < a[ i ]，
          则状态转移方程：dp[ i ]=max(dp[ i ],dp[ j ]+1)。 

class Solution {
public:
    int dp[100005]={0};//dp[i]表示以a[i]为结尾的严格上升子序列的长度
    int LIS(vector<int>& a) {
        int n=a.size();
        int res=0;//初始化
        for(int i=0;i<n;i++){//遍历每个a[i]
            dp[i]=1;//初始化为1
            for(int j=0;j<i;j++){
                if(a[j]<a[i])//确保严格上升
                    dp[i]=max(dp[i],dp[j]+1);
            }
            res=max(res,dp[i]);//维护最大值
        }
        return res;
    }
};



时间复杂度：
空间复杂度：

方法二：
动态规划+二分

思路：
        dp[ i ]存储的长度为i+1的尽可能小的值。
        遍历每个a[ i ]，
        如果严格大于dp[ ]的最后一个数，则加入dp[ ]；
        否则，二分找到dp[ ]中 >= a[ i ] 的数，并用a[ i ]替换。
        最终，dp[ ]的长度即为最长严格上升子序列的长度。


    

 

class Solution {
public:
    int dp[100005]={0};//dp[i]存储的长度为i+1的尽可能小的值
    int LIS(vector<int>& a) {
        int n=a.size();
        if(n==0)
            return 0;
        int len=0;//初始化
        dp[len++]=a[0];//初始化
        for(int i=1;i<n;i++){//遍历每个a[i]
            if(a[i]>dp[len-1]){//如果严格大于dp[]的最后一个数，则加入dp[]
                dp[len++]=a[i];
            }else{//否则，二分找到dp[]中>=a[i]的数，并用a[i]替换
                int l=0,r=len-1,mid;
                while(l<r){
                    mid=(l+r)>>1;
                    if(dp[mid]>=a[i]){
                        r=mid;
                    }else{
                        l=mid+1;
                    }
                }
                dp[l]=a[i];//替换
            }
        }
        return len;
    }
};


时间复杂度：
空间复杂度：