浅析最长上升子序列问题
DP算法解最长上升子序列问题，这里介绍两种算法O(n*n)和O(nlgn)
以poj 2533为例。
O(n*n):
令a[i]为序列的第i个元素，d[i]为以元素a[i]结尾的LIS长度
当0<j<=i-1时：
if(a[j] >= a[i]) then d[i] = 1;
if(a[j] < a[i]) then d[i] = max(d[i],d[j] + 1)
#include<cstdio>#include<iostream>#include<string.h>#include<stdlib.h>#include<algorithm>#define N 1002using namespace std;int a[N],s[N],d[N];int main(void){ int n; scanf("%d",&n); int i,j; for(i=0;i<n;i++)scanf("%d",&a[i]); for(i=1;i<=n;i++)s[i] = 1000000000; int ans = 0; for(i=0;i<n;i++) {j = lower_bound(s+1,s+n+1,a[i]) - s;d[i] = j;s[j] = a[i];ans = max(ans,d[i]); } cout<<ans<<endl; return 0;}