最长上升子序列问题优化

代码+分析

/*  
    最长上升子序列I问题求解思路：
        1、错误思路（已验证）：使用单调栈<-适用范围 返回某一个数左边、右边最近的大于/小于该数的数
        2、正确思路：
            状态表示：dp[j]表示以数字序列中第i个数字结尾的上升子序列
            集合属性：集合上升子序列的最大长度
            状态转移方程：dp[j] = max(dp[j],dp[i]+1),其中 a[i]<a[j]

    最长上升子序列II问题求解思路：
        1、贪心优化
        2、二分查找
*/

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=200010;
int a[N],low[N];


int BinaryS(int i,int j,int x){
    int l=i,r=j,m;
    while( l <= r ){
        m = l + r >> 1;
        if(low[m] < x) l=m+1;
        else r=m-1;
    }
    return r;
}

int main(){
    int n,x,res=0;
    cin>>n;
    memset(low,0x3f,sizeof low);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i = 1 ; i <= n ;i ++){
        int p = BinaryS(1,i-1,a[i]);
        res = max(res,p+1);
        low[p+1]=min(low[p+1],a[i]);
    }

    cout<<res<<endl;
    return 0;
}