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.
Sample Input
71 7 3 5 9 4 8
Sample Output
4
Source
Northeastern Europe 2002, Far-Eastern Subregion
分析：
直接学习该算法即可（这么简单也不好说什么了）
注意要将动规数组f[1000]提前置为1
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
inline int read()
{
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()
{
int n=read(),ans=0;
for(int i=1;i<=n;i++)a[i]=read();
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;
}
优化：
上述算法为最基础，最易理解的一种，时间复杂度为O(N^2)
我们可以将求LIS的程序时间复杂度优化为O(n log n)
推论：将f[x]的值进行分类，对于x的每一个值，我们只需要保留f[x]=k的所有a[t]中的最小值，设long[k]记录这个值，即long[k]=min{a[t]} (f[t]=k)
所以long数组具有如下特点：
1.单调下降
2.有序 long[1]<long[2]<long[3]……<long[n]
3.但它的顺序不确定为当前的最长队列的序
针对第三点，我们需要用link数组来保存当前的最长序列的序号
Link[i]代表连接a[i]的数的序号
当判断a[x]这个元素的最长上升序列时，已知当前最长上升序列列数为MAX，就会出现两种情况：
a[x]>a[MAX]，那么a[x]直接接上a[MAX]，就是最长链
{
MAX++；
Long[MAX]=a[x];
Link[x]=long[MAX-1];
}
a[x]<=a[MAX]，此时在long[1]至long[MAX]中查找出最大的一个数long[i]，并且a[i]<a[x]，则将a[x]接在该元素后面形成更长的链
{
Long[i+1]=x;
Link[x]=long[i];
}
得出序列的编号只需要从最后面的link[MAX]开始查找连接它的序号，就可以得出答案
因为long[]数组是有序的，所以可以使用二分查找法使整个算法时间复杂度降低为O（n log n）
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int a[100001];
int Link[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;
Link[1]=1;
for(i=2;i<=n;i++)
{
if(a[i]>a[Long[Max]])
{
Max++;
Long[Max]=i;
Link[i]=Long[Max-1];
}
else
{
l=find(a[i]);
Long[l+1]=i;
Link[i]=Long[l];
}
}
cout<<Max<<endl;
/* k=Max;
i=Long[Max];
while(Max>0)
{
Long[Max]=a[i];
i=Link[i];
Max--;
}
for(i=1;i<=k;i++)
cout<<Long[i]<<" ";输出序号部分*/
return 0;
}
优化again（其实也不算是优化吧）
贪心的思想，在线读入x，如果x大于a数组里所有的值，就将其放入a数组末尾，否则将第一个小于等于x的a[i]替换为x，维护a数组的单调性，最终a数组内元素的个数就是答案（即最长上升子序列的长度）
注意：a数组内的值并不是最长上升子序列，这种方法只能够求长度！
#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;
}
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr
