求最长上升子序列（LIS上升子序列指的是对于任意的i<j都满足ai<aj的子序列）
代码（70分—超时）
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,ans=-1;
int a[N],dp[N];
int main () {
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=n; i++) {
dp[i]=1;
for(int j=1; j<i; j++)
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
ans=max(dp[i],ans);
}
printf("%d\n",ans);
return 0;
}
AC代码—优化
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,ans,a[N],v[N],s[N];
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=n; i++) {
if(v[i]==1)
continue;
bool flag=false;
for(int j=1; j<=ans; j++)
if(a[i]<s[j]) {
s[j]=a[i];
v[i]=1;
flag=true;
break;
}
if(!flag)
s[++ans]=a[i];
}
printf("%d\n",ans);
return 0;
}
原文：https://www.cnblogs.com/mysh/p/11789477.html