http://acm.pku.edu.cn/JudgeOnline/problem?id=2533
最长上升子序列：
有两种基本方法：两个时间复杂度分别为O(n^2)和O(nlogn)
先来看第1种：
动态规划：
对于给定数列E，元素个数为n,最长上升子序列Q满足对任意1<=i<j<=n，有Q[i]<Q[j]，且E[i]<E[j]。
容易得出O(n^2)的DP递推公式：
D[i]=max{D[j]}+1;(1<=j<i且E[j]<E[i])
D[i]为以元素i结尾的最长子序列个数。
这样经过两重循环一次遍历可以得到最长上升子序列。
代码如下：
#include<iostream>
using namespace std;
int n;
int a[1001],b[1001];
int main()
{ int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=1;
}
for(i=1;i<=n;i++)
{ int maxx=0;
for(j=1;j<=i;j++)
{
if(a[i]>a[j]&&b[j]>maxx)
{ maxx=b[j];
}
}
b[i]=maxx+1;
}
int best=0;
for(i=1;i<=n;i++)
{ if(best<b[i])
best=b[i];
}
printf("%d\n",best);
system("pause");
return 0;
}
第2种方法时间复杂度为O(nlogn)，用到了二分查找和贪心。
其操作如下：
开辟一个栈，每次取栈顶元素s和读到的元素a做比较，如果a>s，则加入栈；如果a<s，则二分查找栈中的比a大的第1个数，并替换。最后序列长度为栈的长度。
这也是很好理解的，对x和y，如果x<y且E[y]<E[x],用E[x]替换E[y],此时的最长序列长度没有改变但序列Q的''潜力''增大。
举例：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，则用3替换5，得到栈中元素为1，3，8，再读6，用6替换8，得到1，3，6，再读7，得到最终栈为1，3，6，7，最长递增子序列为长度4。
代码如下：
#include<iostream>
using namespace std;
int n;
int a[1001],b[1001];
int rear;
int solve(int t)
{ int l=1,r=rear;
while(l<=r)
{ int mid=(l+r)>>1;
if(b[mid]>=t)//若为非递减序列，则为b[mid]>t
r=mid-1;
else
l=mid+1;
}
if(l>rear)
rear=l;
return l;
}
int main()
{ int i,j;
scanf("%d",&n);
rear=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[solve(a[i])]=a[i];
}
printf("%d\n",rear);
system("pause");
return 0;
}