## LeetCode Daily Challenge 2024/10/30
#### 1671. Minimum Number of Removals to Make Mountain Array
---
### main idea : LIS/LDS
* approach : keep track of the maximum of a increasing sequence
* example : given a sequence of numbers : `[0, 1, 3, 5, 9, 15, 16, 4, 10, 11, 12, 13, 14]`
* situation : `arr = [0, 1, 3, 5, 9, 15, 16]`
* Note that :
>The index of a number x means that if a sequence ends with x, then its maximum increasing length equals the index + 1.
>For example, the maximum length of a sequence that ends with 15 is [0, 1, 3, 5, 9, 15], and the index + 1 is the length of the sequence.sequence.
* Next number = 4
* It can easily be observed that 4 and 5 are larger than [0, 1, 3]; moreover, a sequence that ends with 4 is more likely to be smaller than the next number.
* Operation: Find the upper bound of the original sequence and change it to the number 4.

### Code:

import java.util.ArrayList;
class Solution {
    public int minimumMountainRemovals(int[] nums) {
        ArrayList<Integer> arr_I = new ArrayList<>();
        ArrayList<Integer> arr_D = new ArrayList<>();

        int[] LIS = new int[nums.length];
        int[] LDS = new int[nums.length];
        
        arr_I.add(nums[0]);
        LIS[0] = 1;
        for (int i = 1; i < nums.length; i++) { // LIS
        
            int target = arr_I.size();
            for (int jump = arr_I.size(); jump > 0; jump /= 2) {
                while (target - jump >= 0 && arr_I.get(target - jump) >= nums[i]) {
                    target -= jump;
                }
            }

            LIS[i] = target + 1;
            if (target == arr_I.size()) arr_I.add(nums[i]);
            else arr_I.set(target, nums[i]);
        }

        arr_D.add(nums[nums.length - 1]);
        LDS[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) { // LDS(LIS from back)
        
            int target = arr_D.size();
            for (int jump = arr_D.size(); jump > 0; jump /= 2) {
                while (target - jump >= 0 && arr_D.get(target - jump) >= nums[i]) {
                    target -= jump;
                }
            }

            LDS[i] = target + 1;
            if (target == arr_D.size()) arr_D.add(nums[i]);
            else arr_D.set(target, nums[i]);
        }

        int min = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length - 1; i++) {
            // peak cannot be the leftmost & rightmost
            if (LIS[i] != 1 && LDS[i] != 1) min = Math.min(min, nums.length - (LIS[i] + LDS[i]) + 1);
        }

        return min;
    }
}