题目链接： http://poj.org/problem?id=2533
题意：第一个数n，接下来n个数，> ....求最长上升子序列。
这道题有两种解法，第一种是通解，也适用于别的LIS。
代码1：
#include<cstdio> #include<algorithm> using namespace std; int a[1005],dp[1005]; int main() { int n; while(scanf("%d",&n)==1) { for(int i=1; i<=n; i++) { scanf("%d",&a[i]); dp[i]=1; } int len=1; for(int i=1; i<=n; i++) { for(int j=1; j<i; j++) { if(a[i]>a[j]) { if(dp[j]+1>=dp[i]) /// dp[i]=max(dp[i],dp[j]+1); dp[i]=dp[j]+1,dp[j]; } len=max(len,dp[i]); } } printf("%d\n",len); } return 0; }
代码2：
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> using namespace std; int a[1005],dp[1005]; int main() { int n,len; while(scanf("%d",&n)==1) { for(int i=1; i<=n; i++) scanf("%d",a+i); dp[1]=a[1]; len=1; for(int i=2; i<=n; i++) if(a[i]>dp[len]) dp[++len]=a[i]; else dp[lower_bound(dp+1,dp+len+1,a[i])-dp]=a[i]; printf("%d\n",len); } return 0; }
原文：http://www.cnblogs.com/a-clown/p/5988179.html