CP003201.LIS最长上升子序列

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N], n, a[N], ans=1;
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		scanf("%d",a+i);
	}
	//状态转移
	//以a[i]结尾的数字的LIS长度
	for(int i=1; i<=n; i++) {
		f[i]=1;
		//遍历前i-1个数，看接在那个数后面最大
		for(int j=1; j<=i-1; j++) {
			if(a[i]>a[j]) {
				f[i]=max(f[j]+1,f[i]);
			}
		}
		ans=max(ans,f[i]);
	}
	printf("%d",ans);
	return 0;
}