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


	arr.length &gt;= 3
	There exists some index i (0-indexed) with 0 &lt; i &lt; arr.length - 1 such that:
	
		arr[0] &lt; arr[1] &lt; ... &lt; arr[i - 1] &lt; arr[i]
		arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]
	
	


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

&nbsp;
Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.


Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].


&nbsp;
Constraints:


	3 &lt;= nums.length &lt;= 1000
	1 &lt;= nums[i] &lt;= 109
	It is guaranteed that you can make a mountain array out of nums.


class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        inc = [0] * n
        dec = [0] * n
        
#  Longest Increasing Subsequence
        for i in range(1,n):
            for j in range(0,i):
                if nums[i] > nums[j]:
                    inc[i] = max(inc[i], inc[j] + 1)
                
#  Longest Decreasing Subsequence
        for i in range(n-2,-1,-1):
            for j in range(n-1,i,-1):
                if nums[i] > nums[j]:
                    dec[i] = max(dec[i], dec[j] + 1)
        
# Final calculation
        res = 0
        for i in range(0,n):
            if inc[i] > 0 and dec[i] > 0:
                res = max(res, inc[i] + dec[i])
                
# Final conclusion        
        return n - res - 1
class Solution {
    public int minimumMountainRemovals(int[] nums) {

        int n = nums.length;
        int[] LIS = new int[n];
        int[] LDS = new int[n];

        Arrays.fill(LIS, 1);
        Arrays.fill(LDS, 1);
        // calculate the longest increase subsequence (LIS) for every index i
        for(int i=1 ; i < n ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(nums[i] > nums[j] && LIS[j]+1 > LIS[i])
                    LIS[i] = LIS[j]+1;
            }
        }

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

            if(LIS[i] > 1 && LDS[i] > 1)
                max = Math.max(LIS[i]+LDS[i]-1, max);
        }
        return n - max;
    }
}
class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();

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

        // LIS from front
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<i; j++)
            {
                if(nums[i] > nums[j] && 1 + dp1[j] > dp1[i])
                {
                    dp1[i] = 1 + dp1[j];
                }
            }
        }

        //LIS from back
        for(int i=n-1; i>=0; i--)
        {
            for(int j=n-1; j>i; j--)
            {
                if(nums[i] > nums[j] && dp2[j] + 1 > dp2[i]){
                    dp2[i] = dp2[j] + 1;
                }
            }
        }

        int maxi = 1;
        for(int i=0; i<n; i++){
            if(dp1[i] > 1 && dp2[i] > 1){
                maxi = max(maxi, dp1[i] + dp2[i] -1);
            }
        }
        return (n-maxi);
    }
};
var minimumMountainRemovals = function(nums) {
    let n=nums.length
    let previous=Array.from({length:n},item=>1)
    let previous2=Array.from({length:n},item=>1)
    //calcultaing left and right side LIS in single iteration
    for (let i=0;i<n;i++){
        for (let j=0;j<i;j++){
            //reverse indexes
            let i2=n-1-i
            let j2=n-1-j
            //calculating first dp serially 
            if (nums[i]>nums[j] && previous[i]<previous[j]+1){
                previous[i]=previous[j]+1
            }
            //calculating second dp reversely
            if (nums[i2]>nums[j2] && previous2[i2]<previous2[j2]+1){
                previous2[i2]=previous2[j2]+1
            }
        }
    }
    let max=0
    for (let i=0;i<n;i++){
        //golden condition// to avoid only increasing and decreasing
        //because if a combination of 1 indicates its increasing fully or decreasing !
        if (previous[i]>1 && previous2[i]>1){
        //at a specific index highest increasing will come from left LIS
        // and highest decreasing will come from right side LIS
        max=Math.max(max,previous[i]+previous2[i]-1)
        }
    }
    return n-max //we need to remove the rest from total
};
Minimum Number of Removals to Make Mountain Array