最长上升子序列
sequence.pas/c/cpp
【题目描述】
一个数的序列B=(b1 , b2 , ... , bS)，当b1 < b2 < ...< bS 的时候，我们称这个序列是上升的。对于给定的一个序列A=(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... <iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1,
7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。你的任务，就是对于给定的序列，求出最长上升子序列的长度。
【输入】
输入文件：sequence.in
输入的第一行包括一个整数，N。表示序列的长度。
第二行包括N 个互不相同的整数，即给定的序列。
【输出】
输入文件：sequence.out
输出为一行，包含一个整数。表示最长上升子序列的长度。
【输入样例】
7
1 7 3 5 9 4 8
【输出样例】
4
【数据范围】
对于100%的数据，1<=N<=1000，序列中的每个整数的取值范围是[0,10000]。
同类题目扩展：http://blog.csdn.net/yuyanggo/article/details/8598045
解析：这是一道比较裸的线型动态规划。
比较朴素的做法是用f[i]记录以i号点为最后一个节点的序列最长长度，主代码如下：
Pascal: c++:
Fori:=1 to n do for(i=1;i<=n;i++) f[i]=1;
f[i]:=1;
For i:=1 to n do for(i=1;i<=n;i++)
For j:=1 to i-1 do for(j=1;j<i:j++)
If ((a[j]<a[i])and (f[i]<f[j]+1)) then if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
F[i]:=f[j]+1;
Max:=1; intMax=1;
For i:=1 to n do for(i=1;i<=n;i++)
If f[i]>max then max:=f[i]; Max=max(Max,f[i]);
Writeln(max); printf(“%d\n”,Max);
按照上面的方法，时间复杂度接近o(n*(n-1))/2,有无办法时期变得更优呢？--------单调队列。
我们开一个递增的单调队列，当遇到节点i时，如果a[i]>q[r],那么将i号点插入队尾，队列元素加1，否则，就在队列中找到从左数第一个大于a[i]的数，把他的值赋为a[i], R-L就表示当前最长上升子序列长度，答案就是最终的队列长度。这样做为什么是对的呢？
以一组样例为例：2 3 1 2 4
读入1号点，L=1,R=1,q[1]=2
读入2号点，L=1,R=2,q[2]=3
读入3号点，将q[1]的值赋为1，此时序列长度为二，依然为当前最长上升子序列长度
读入4号点，将q[2]的值赋为3，此时序列长度为二，依然为当前最长上升子序列长度
读入5号点，将4加入队列，q[3]=4, 此时序列长度为3.
所以最终答案就是3.
代码实现：
单调队列+二分查找
#include<cstdio>
#define maxn 1000+10
using namespace std;
int q[maxn],p=1;//用p表示队列长度
void init()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
}
int find(int x)//二分查找
{
int l=1,r=p,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(x>q[mid])
l=mid+1;
else
r=mid-1;
}
return l;
}
void work()
{
int n;
scanf("%d",&n);
scanf("%d",&q[1]);
int i,a;
for(i=2;i<=n;i++)
{
scanf("%d",&a);
if(a>q[p])q[++p]=a;//比队列中最大的数还要大，就直接加入队尾
else if(a<q[p])q[find(a)]=a;//查找从左数第一个大于a的数的位置并赋值
}
printf("%d\n",p);
}
int main()
{
init();
work();
return 0;
}