3051: 登山 有点难这还是入门题吗？

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int main(){
    // 定义变量n表示数组长度，a、b、c为辅助数组，max用于存储最大值
    int n, a[1100], b[1100], c[1100], max = 0;
    // 输入数组长度n
    cin >> n;
    // 输入数组a的元素
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    // 计算数组b，b[i]表示以a[i]结尾的最长递增子序列的长度
    for(int i = 1; i <= n; i++){
        b[i] = 1; // 初始化b[i]为1
        for(int j = 1; j <= i - 1; j++){
            // 如果a[i]大于a[j]且b[i]小于b[j]+1，则更新b[i]
            if(a[i] > a[j] && b[i] < b[j] + 1){
                b[i] = b[j] + 1;
            }
        }
    }
    // 计算数组c，c[i]表示以a[i]开头的最长递减子序列的长度
    for(int i = n; i >= 1; i--){
        c[i] = 1; // 初始化c[i]为1
        for(int j = i + 1; j <= n; j++){
            // 如果a[j]小于a[i]且c[i]小于c[j]+1，则更新c[i]
            if(a[j] < a[i] && c[i] < c[j] + 1){
                c[i] = c[j] + 1;
            }
        }
    }
    // 计算最大值max，即最长的“山”形子序列的长度
    for(int i = 1; i <= n; i++){
        // 如果当前b[i] + c[i] - 1大于max，则更新max
        if(max < b[i] + c[i] - 1){
            max = b[i] + c[i] - 1;
        }
    }
    // 输出最大值max
    cout << max << endl;
    return 0;
}