最长递增子序列-蒲公英云

最长递增子序列

灰太狼 2022-06-12 11:23 378阅读 0赞

给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）

例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。

Input

第1行：1个数N，N为序列的长度(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S i i <= 10^9)

Output

输出最长递增子序列的长度。

Sample Input

Sample Output

5
//#include<cstdio>
//#include<algorithm>
//using namespace std;
//int dp[50005];
//int a[50005];
//int main()
//{
//    int n,len=1;
//    scanf("%d",&n);
//    for(int i=1;i<=n;i++)
//        scanf("%d",&a[i]);
//    dp[len]=a[1];
//    for(int i=1;i<=n;i++)
//    {
//        if(a[i]>dp[len])
//          dp[++len]=a[i];
//        else
//        {
//            int pos=lower_bound(dp+1,dp+len,a[i])-dp;
//            dp[pos]=a[i];
//        }
//    }
//    printf("%d\n",len);
//    return 0;
// }
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int arr[50005],ans[50005],len;
int A(int i)
{
    int left,right,mid;
    left=0,right=len;
    while(left<right)
    {
        mid = left+(right-left)/2;
        if(ans[mid]>=arr[i]) right=mid;
        else left=mid+1;
    }
    return left;
}
int main()
{
    int n,i,j;
    while(~scanf("%d",&n))
    {
        for(i=0; i<n; ++i)//这里也是最好从0开始，二分的时候一般是从0开始的，错了我10次好气人！！！
            scanf("%d",&arr[i]);
        ans[0] = arr[0];
        len=0;
        int pos;
        int maxx=0;
        for(i=0; i<n; ++i)
        {
            if(arr[i]>ans[len])
                ans[++len]=arr[i];
            else
            {
                int pos=A(i);
                //pos=lower_bound(ans,ans+len,arr[i])-ans;//这里一定要注意下标最好是统一从0开始,反正就是要统一，不可以一个是从0开始一个是从1开始,
                ans[pos] = arr[i];
            }
            if(maxx<len)
                maxx=len;
        }
        printf("%d\n",maxx+1);
    }
    return 0;
}