Minimum Number of Removals to Make Mountain Array LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minimumMountainRemovals(vector<int> &nums) {
4
    int n = nums.size();
5

6
    vector<int> dp1(n, 1), dp2(n, 1);
7

8
    // LIS from front
9
    for (int i = 0; i < n; i++) {
10
      for (int j = 0; j < i; j++) {
11
        if (nums[i] > nums[j] && 1 + dp1[j] > dp1[i]) {
12
          dp1[i] = 1 + dp1[j];
13
        }
14
      }
15
    }
16

17
    // LIS from back
18
    for (int i = n - 1; i >= 0; i--) {
19
      for (int j = n - 1; j > i; j--) {
20
        if (nums[i] > nums[j] && dp2[j] + 1 > dp2[i]) {
21
          dp2[i] = dp2[j] + 1;
22
        }
23
      }
24
    }
25

26
    int maxi = 1;
27
    for (int i = 0; i < n; i++) {
28
      if (dp1[i] > 1 && dp2[i] > 1) {
29
        maxi = max(maxi, dp1[i] + dp2[i] - 1);
30
      }
31
    }
32
    return (n - maxi);
33
  }
34
};