题解 | #合唱队#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, tmp;
    int i, j;
    vector<int> heights;
    // 输入
    while(cin >> n){
        for(i = 0; i < n; i++){
            cin >> tmp;
            heights.push_back(tmp);
        }
        // 设置两个dp数组
        vector<int> dp_h(n, 1), dp_t(n, 1);
        // 正序遍历
        for(i = 0; i < n; i++){
            for(j = 0; j < i; j++){
                if(heights[i] > heights[j]){
                    dp_h[i] = max(dp_h[i], dp_h[j] + 1);//比较{原始dp_h[i]的值，还是dp_h[j]结果加上选i这个位置}，谁更大，更新到dp_h[i]中
                }
            }
        }
        // 逆序遍历
        for(i = n-1; i >= 0; i--){
            for(j = n-1; j > i; j--){
                if(heights[i] > heights[j]){
                    dp_t[i] = max(dp_t[i], dp_t[j] + 1);
                }
            }
        }
        // 求和得到最长先增后减子序列的长度
        int maxNum = 0;
        for(i = 0; i < n; i++){
            if(dp_t[i] + dp_h[i] - 1 > maxNum)
                maxNum = dp_t[i] + dp_h[i] - 1;
        }
        // 输出
        cout << n - maxNum << endl;
        // 清除vector，以供下一轮使用
        heights.clear();
    }
    return 0;
}