技术教程 编程教程 [ACM]NEFUOJ-最长上升子序列 正文

[ACM]NEFUOJ-最长上升子序列

2023-06-13,,

Description

给出长度为n的数组，找出这个数组的最长上升子序列

Input

第一行：输入N，为数组的长度(2=<N<=50000)

第二行：N个值，表示数组中元素的值(109<=a[i]<=109)

Output

输出最长上升子序列的长度

Sample Input

5

-6 4 -2 10 5

Sample Output

3



#include<iostream>

#include<cstring>

#include<algorithm>  

using namespace std;  

const int INF=0x7f7f7f7f;

const int maxn=50005;

int n, g[maxn], d[maxn],a[maxn];  

int main()

{

	cin>>n;

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

	{

		cin>>a[i];

	}

    fill(g, g+n, INF);

    int maxnum=-1;

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

    {

        int j = lower_bound(g, g+n, a[i]) - g;

        d[i] = j+1;

        if(maxnum<d[i])

            maxnum=d[i];

        g[j] = a[i];

    }

    cout<<maxnum<<endl;

    return 0;

}

[ACM]NEFUOJ-最长上升子序列的相关教程结束。

《[ACM]NEFUOJ-最长上升子序列.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!