题解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}

// up[i]表示以第i个景点结尾的上升序列的最大长度
vector<int> up(n, 1);
// down[i]表示以第i个景点结尾的下降序列的最大长度
vector<int> down(n, 0);

// 计算上升序列
for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (h[i] > h[j]) {
            up[i] = max(up[i], up[j] + 1);
        }
    }
}

// 计算下降序列
for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (h[i] < h[j]) {
            // 情况1：从上升序列的最高点j开始下降到i
            down[i] = max(down[i], up[j] + 1);
            // 情况2：从某个下降序列的中间点j继续下降到i
            down[i] = max(down[i], down[j] + 1);
        }
    }
}

// 找出最大值
int ans = 0;
// 上升序列的最大值
for (int i = 0; i < n; i++) {
    ans = max(ans, up[i]);
}
// 下降序列的最大值
for (int i = 0; i < n; i++) {
    ans = max(ans, down[i]);
}

cout << ans << endl;
return 0;

}