蓝桥杯算法提高VIP-聪明的美食家 （C++代码）

解题思路:

注意事项:

参考代码:

#include <algorithm>
#include <iostream>
using namespace std;
int arr[1000];
int dp[1000];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		dp[i] = 1;		//dp序列初始化为1
	}
		
	for (int i = 2; i <= n; i++) { 
		int maxx = 0;
		for (int j = 1; j <= i - 1; j++) {
			if (arr[j] <= arr[i] && dp[j] > maxx)//在1-i-1找到最大序列  累加
				maxx = dp[j];
		}
		dp[i] += maxx; //找到最大累加
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) //在1-n寻找最大序列的值
		ans = max(ans, dp[i]);
	cout << ans<<endl;
	return 0;
}