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

方法一：
动态规划


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



#include <bits/stdc++.h>

using namespace std;

int n,a[205],dp[205];//dp[i]表示以a[i]为结尾的严格上升子序列的长度

int main(){
    
    while(cin >> n){
        int res=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        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]);//维护最大值
        }
        cout << res << endl;
    }
    
    return 0;
}


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


方法二：
动态规划+二分

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


    

#include <bits/stdc++.h>

using namespace std;

int n,a[205],dp[205];//dp[i]存储的长度为i+1的尽可能小的值

int main(){
    
    while(cin >> n){
        int len=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        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];//替换
            }
        }
        cout << len << endl;
    }
    
    return 0;
}



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