Minimum Number of Removals to Make Mountain Array LeetCode solution in Java

1
class Solution {
2
  public int minimumMountainRemovals(int[] nums) {
3

4
    int n = nums.length;
5
    int[] LIS = new int[n];
6
    int[] LDS = new int[n];
7

8
    Arrays.fill(LIS, 1);
9
    Arrays.fill(LDS, 1);
10
    // calculate the longest increase subsequence (LIS) for every index i
11
    for (int i = 1; i < n; i++) {
12
      for (int j = 0; j < i; j++) {
13
        if (nums[i] > nums[j] && LIS[j] + 1 > LIS[i]) LIS[i] = LIS[j] + 1;
14
      }
15
    }
16

17
    // calculate the longest decreasing subsequence(LDS) for every index i and keep track of the
18
    // maximum of LIS+LDS
19
    int max = 0;
20
    for (int i = n - 2; i >= 0; i--) {
21
      for (int j = n - 1; j > i; j--) {
22
        if (nums[i] > nums[j] && LDS[j] + 1 > LDS[i]) LDS[i] = LDS[j] + 1;
23
      }
24

25
      if (LIS[i] > 1 && LDS[i] > 1) max = Math.max(LIS[i] + LDS[i] - 1, max);
26
    }
27
    return n - max;
28
  }
29
}