1671. Minimum Number of Removals to Make Mountain Array

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:

• arr[0] < arr[1] < … < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > … > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums​​​ a mountain array.

c++

class Solution {
    void lis(vector<int>& lis, int n) {
        auto it = lower_bound(lis.begin(), lis.end(), n);
        if(it == end(lis)) lis.push_back(n);
        else *it = n;
    }
public:
    int minimumMountainRemovals(vector<int>& A) {
        int n = A.size(), res = INT_MAX;
        vector<int> l, r, dp(n);
        for(int i = 0; i < n; i++) {
            lis(l,A[i]);
            dp[i] = l.size();
        }
        for(int i = n - 1; i >= 0; i--) {
            lis(r,A[i]);
            if(dp[i] > 1 and r.size() > 1)
                res = min(res, n - (dp[i] + (int)r.size() - 1));
        }
        return res;
    }
};