3050: 最长上升子序列

解题思路:经典DP

注意事项:答案不是f[n], 而是f数组的最大值

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int a[N],f[N];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++)
	{
		f[i] = 1;
		for(int j = 1; j < i; j ++){
			if(a[j] < a[i])
				f[i] = max(f[i], f[j] + 1);
		}
	}
	int mx = f[1];
	for(int i = 1; i <= n; i ++) if(mx < f[i]) mx = f[i];
	cout << mx;
	return 0;
}