POJ 2533 Longest Ordered Subsequence LIS O(n*log(n))

2024-10-21 03:38:05

最长上升子序列O(n*log(n))的做法，只能用于求长度不能求序列。

#include <iostream>

#include <algorithm>

using namespace std;

const int N=;

int s[N],x;

int main()

{

    int n;

    while(cin>>n){

        int top=;

        for(int i=;i<n;i++){

            cin>>x;

            if(top==||s[top-]<x) s[top++]=x;

            else s[upper_bound(s,s+top,x)-s]=x;

        }

        cout<<top<<endl;

    }

    return ;

}

最新文章

热门文章