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;
}