华为机试：合唱队

//chatGPT帮大忙

重新看这道题，觉得解法有问题，不知道为什么测试用例没有被卡，dp_left/right数组的下标+1表示的才是左边/右边能站的最多人数，不能直接使用tail数组的长度表示最多人数。

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

int main() {
    int N, i, j, temp, ans;
    cin >> N;
    ans = N;
    vector<int> height;
    for (i = 0; i < N; i++) {
        cin >> temp;
        height.push_back(temp);
    }
    vector<int> tails;
    vector<int> dp_left(N, 0);
    for (i = 0; i < N; i++) {
        auto it = lower_bound(tails.begin(), tails.end(), height[i]);
        if (it == tails.end()) {
            tails.push_back(height[i]);
            dp_left[i] = tails.size();
        } else {
            *it = height[i];
            dp_left[i] = it - tails.begin();
        }
        //dp_left[i] = tails.size();
    }
    // for (i = 1; i < N; i++) {
    //     for (j = 0; j < i; j++) {
    //         if (height[j] < height[i]) {
    //             dp_left[i] = max(dp_left[i], dp_left[j] + 1);
    //         }
    //     }
    // }
    tails.clear();
    vector<int> dp_right(N, 0);
    for (i = N-1; i >= 0; i--) {
        auto it = lower_bound(tails.begin(), tails.end(), height[i]);
        if (it == tails.end()) {
            tails.push_back(height[i]);
            dp_right[i] = tails.size();
        } else {
            *it = height[i];
            dp_right[i] = it - tails.begin();
        }
        //dp_right[i] = tails.size();
    }
    // for (i = N - 2 ; i >= 0; i--) {
    //     for (j = N - 1; j > i; j--) {
    //         if (height[j] < height[i]) {
    //             dp_right[i] = max(dp_right[i], dp_right[j] + 1);
    //         }
    //     }
    // }
    for (i = 0; i < N; i++) {
        ans = min(ans, N - (dp_left[i] + dp_right[i] - 1));
    }
    cout << ans << endl;
    return 0;
}