题解

按照老师的方法老老实实做

#include <iostream>
#include <cstdio>
using namespace std;
int a[1005], dp[2][1005];//dp[0][i]表示不取第i个数时的最大值，dp[1][i]表示取第i个数时的最大值
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);//不取肯定是上一个的长度最大值
		for(int j = 0; j < i; j++){
			if(a[j] < a[i]) dp[1][i] = max(dp[1][i], dp[1][j] + 1);//取的话就找比它小的而且取了的长度最大值
		}
	}
	cout << max(dp[0][n], dp[1][n]);//输出结果

	return 0;
}