题解 | #合唱队#

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


vector<int> LTS(vector<int>& nums){
    int n = nums.size();
    vector<int> dp(n,1);
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(nums[j] < nums[i]){
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
    }
    return dp;
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        vector<int> nums1(n), nums2(n);
        for (int i = 0, j = n - 1; i < n && j >= 0; i++, j--) {
            cin >> nums1[i];
            nums2[j] = nums1[i];
        }
        auto dp1 = LTS(nums1);
        auto dp2 = LTS(nums2);
        int maxLen = 0;
        for(int i = 0, j = n - 1;i < n && j >=0; i++,j--){
            maxLen = max(maxLen, dp1[i] + dp2[j] - 1); 
        }

        cout << n - maxLen << endl;
    }
}
// 64 位输出请用 printf("%lld")
// 0   1   2   3   4
// 186 186 150 200 160 130 197 200
// 0   1   2    2   3   5   4

最长上升子序列