给定一个序列,求最少去掉多少个数,使得剩下的数满足先单增后单减,写出c++代码，时间复杂度低

以下是一种时间复杂度为 O(nlogn) 的动态规划解法：

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

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    vector<int> dp1(n, 1); // 记录单增子序列的长度
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp1[i] = max(dp1[i], dp1[j] + 1);
            }
        }
    }

    vector<int> dp2(n, 1); // 记录单减子序列的长度
    for (int i = n - 2; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (nums[j] < nums[i]) {
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp1[i] + dp2[i] - 1); // 减去重复的 nums[i]
    }

    cout << n - ans << endl; // 去掉的数的个数

    return 0;
}

思路是先用动态规划求出以每个数结尾的最长单增子序列和最长单减子序列的长度，然后遍历每个数，计算出以该数为峰值的最长先单增后单减子序列的长度，并记录答案。最后，去掉的数的个数即为 n 减去最长先单增后单减子序列的长度。