我们定义 arr 是 山形数组 当且仅当它满足：
arr.length >= 3
存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]
给你整数数组 nums? ，请你返回将 nums 变成 山形状数组 的? 最少 删除次数。
示例 1：
输入：nums = [1,3,1]
输出：0
解释：数组本身就是山形数组，所以我们不需要删除任何元素。
示例 2：
输入：nums = [2,1,1,5,6,2,3,1]
输出：3
解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。
提示：
3 <= nums.length <= 1000
1 <= nums[i] <= 109
题目保证 nums 删除一些元素后一定能得到山形数组。
开始想到了动态规划来做，还是wa了，参考了题解，希望下次能单人AC个hard题：
class Solution {
public:
int minimumMountainRemovals(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, 1), right(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
left[i] = max(left[i], left[j] + 1);
}
}
}
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] > nums[j]) {
right[i] = max(right[i], right[j] + 1);
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (left[i] > 1 && right[i] > 1) {
ans = max(ans, left[i] + right[i] - 1);
}
}
return n - ans;
}
};
还有二分查找的方法，以及前后缀分解，具体读者可以去看看灵神的题解：前后缀分解+最长递增子序列