# Poj2533最长上升子序列

Posted by yjjr's blog on February 6, 2018

# POJ2533最长上升子序列

http://www.sakurasake.icoc.me/nd.jsp?id=1#_np=2_327

## Longest Ordered Subsequence

### Description

A numeric sequence ofai is ordered if a1 < a2 < ... <aN. Let the subsequence of the given numeric sequence (a1,a2, ...,aN) be any sequence (ai1, ai2, ..., aiK), where 1 <=i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

### Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

### Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

71 7 3 5 9 4 8

4

### Source

Northeastern Europe 2002, Far-Eastern Subregion

#### 分析：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a[10005],f[10005];
int main()
{
for(int i=1;i<=n;i++)f[i]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]<a[i])f[i]=max(f[j]+1,f[i]);
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
cout<<ans;
}

1.单调下降

2.有序 long[1]<long[2]<long[3]……<long[n]

3.但它的顺序不确定为当前的最长队列的序

a[x]>a[MAX]，那么a[x]直接接上a[MAX]，就是最长链

{

MAX++；

Long[MAX]=a[x];

}

a[x]<=a[MAX]，此时在long[1]至long[MAX]中查找出最大的一个数long[i]，并且a[i]<a[x]，则将a[x]接在该元素后面形成更长的链

{

Long[i+1]=x;

}

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int a[100001];
int Long[100001];
int n,Max;

int find(int key)
{
int L=1,R=Max,mid;
while(L<=R)
{
mid=(L+R)/2;
if(a[Long[mid]]<key)L=mid+1;
else R=mid-1;
}
return L-1;
}

int main()
{
int i,j,k,l;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
Max=1;
Long[Max]=1;
for(i=2;i<=n;i++)
{
if(a[i]>a[Long[Max]])
{
Max++;
Long[Max]=i;
}
else
{
l=find(a[i]);
Long[l+1]=i;
}
}
cout<<Max<<endl;
/*  k=Max;
i=Long[Max];
while(Max>0)
{
Long[Max]=a[i];
Max--;
}
for(i=1;i<=k;i++)
cout<<Long[i]<<" ";输出序号部分*/
return 0;
}

#### 优化again（其实也不算是优化吧）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define inf 0x7fffffff
using namespace std;
int a[100005],n,x,num=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)a[i]=inf;
for(int i=1;i<=n;i++)
{
cin>>x;
int flag=0,j;
for(j=1;j<=num;j++)
if(x<=a[j]){a[j]=x;break;}else continue;
if(j>num){num++;a[num]=x;}
}
cout<<num<<endl;
return 0;
}