AcWing.895.最长上升子序列

给定一个长度为?N?的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数?N。

第二行包含?N?个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000，
-≤数列中的数≤

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

用f[i]表示以第i个数结尾的上升子序列的最长长度

如果选定了第i个数，那么其前面就有? 前面有0个数，前面倒数第二个数是a[1]，是a[2]，是a[3]...倒数第二个数是a[i-1]

也就是子序列以第1个数结尾，以第2个数结尾，......以a[i-1]结尾，其结果必定有可能存在不符合的部分，舍去即可

如果我们有...a[j],a[i]是符合的，也就是a[i]的子序列以a[j]结尾且a[j] < a[i]，那么a[i]的子序列最大长度就是f[j]+1，故可得状态转移方程为：

f[i] = max(f[j]+1) ，j = 0,1,2,......i-1;

#include<iostream>
using namespace std;
const int N = 1000 + 10;

int f[N];
int a[N];
int n;

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++) {
		f[i] = 1;	//如果以a[i]结尾的上升子序列里只有他自己，那么长度为1
		for (int j = 1; j <= i - 1; j++) {	//遍历前面的数
			if (a[j] < a[i]) {		//如果满足上升子序列的条件
				f[i] = max(f[i], f[j] + 1);//状态转移方程
			}
		}
	}

	int ans = 0;

	//遍历以所有数结尾的上升子序列的最大长度
	for (int i = 1; i <= n; i++) {	
		ans = max(ans, f[i]);	//取其中最大值
	}

	cout << ans;
	return 0;
}

?