## Introduction

In this article, we will discuss a very good problem: Minimum number of removals to make a mountain array

Mountain array is an array where,

There exists some index i with 0 < i < arr.size - 1 where,

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

### Problem Statement

Given an integer array arr, return the minimum number of elements to remove to make arrâ€‹â€‹â€‹ a mountain array.

Sample Example**Example 1:**

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

**Example 2:**

```
Input: arr = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: Remove the elements at indices 0, 1, and 5, making the array arr = [1,5,6,3,1].
```

## Approach

The basic idea to solve this problem will be to find the longest mountain subsequence first then remove it from the total number of elements of an array.

Therefore the number of removals = **Total length of given array****- (longest mountain subsequence)**.

To calculate the longest mountain subsequence, first, calculate the longest increasing subsequence from left for each index and store it in an array(say, dpleft). Similarly, calculate the longest increasing subsequence from left for each index and store it in an array(say, dpright).

Now consider each 0<i<n to be the middle of a mountain subsequence with the length of subsequence as dpleft[i]+dright[i]-1 (we subtract 1 to not double count the middle element).

However, we will check for i only if dpleft[i]>1 and dpright[i]>1 because the sequence is not a mountain sequence, and removing conditions can give inconsistent results if either dpleft[i] or dpright[i] = 1, then it means that the sequence is either strictly increasing or decreasing.

For an efficient approach, you can refer to __Minimum Number of Removals to Make Mountain Array - Part 2____.__

### Algorithm

- Take all the inputs in the given format.
- Declare two arrays
**dpleft**and**dpright**, to store LIS from left and right, respectively. -
Fill dpleft and dpright with LIS for each index, and this can be done with
__the DP solution of LIS__. - Traverse each index of the array, and check the length of the maximum mountain array for each index.
- Length of each mountain array will be, dpleft[i]+dright[i]-1 , after checking condition only if dpleft[i]>1 and dpright[i]>1.
- Store max_length in variable and keep updating it accordingly.
- Output N - max_length, that we required result.