题解 | 合唱队

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

int main() {
    int n;
    while (cin >> n) {
        // 输入的数组
        int tmp;
        vector<int> nums;
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            nums.push_back(tmp);
        }

        // 求左到右以i为结尾的最长递增子序列
        vector<int> dp1(n, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                }
            }
        }

        // 求从左到右以i为开始的最长递减子序列
        vector<int> dp2(n, 1);
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
        }

        // 寻找递增和递减子序列的和的最大值，由于第i个位置算了两次，需要再减1，得到队列最大长度
        int maxSeq = 0;
        for (int i = 0; i < n; i++) {
            maxSeq = max(maxSeq, dp1[i] + dp2[i]);
        }
        maxSeq -= 1;
        cout << n - maxSeq << endl;
    }
    return 0;
}