【題解】LeetCode 1671. Minimum Number of Removals to Make Mountain Array

class Solution {
public:
    int minimumMountainRemovals(vector<int>& a) {
        vector <int> v;
        int l[1005], r[1005], ans = 1000;
        for (int i = 0; i < a.size(); i++){
            if (v.empty() || a[i] > v.back()){
                v.push_back(a[i]);
                l[i] = v.size();
            }
            else{
                int idx = lower_bound(v.begin(), v.end(), a[i])-v.begin();
                v[idx] = a[i];
                l[i] = idx+1;
            }
        }
        v.clear();
        for (int i = a.size()-1; i >= 0; i--){
            if (v.empty() || a[i] > v.back()){
                v.push_back(a[i]);
                r[i] = v.size();
            }
            else{
                int idx = lower_bound(v.begin(), v.end(), a[i])-v.begin();
                v[idx] = a[i];
                r[i] = idx+1;
            }
        }
        for (int i = 1; i < a.size()-1; i++){
            ans = min(ans, (int)a.size()-(l[i]+r[i]-1));
        }
        return ans;
    }
};