This is an example of using dynammic programming to solve a problem using the Longest Increasing Subsequence to solve.
Problem
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given an integer array nums, return the minimum number of elements to remove to make nums a mountain array.
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].
Constraints:
3 <= nums.length <= 1000
1 <= nums[i] <= 109
It is guaranteed that you can make a mountain array out of nums.
Discussion
To solve, we apply the Longest Increasing Subsequence from the front and from behind, add them and subtract from the length of the array.
Solution
Java
class Solution { public int minimumMountainRemovals(int[] sequence) { int [] lengthsFromFront= new int[sequence.length]; int [] lengthsFromBehind= new int[sequence.length]; int maxLength=1; for(int i=0;i<lengthsFromFront.length;i++)lengthsFromFront[i]=1; for(int i=0;i<lengthsFromBehind.length;i++)lengthsFromBehind[i]=1; for(int i=0;i<sequence.length;i++){ for(int j=i-1;j>=0;j--){ if(sequence[j]<sequence[i] && lengthsFromFront[i]<=lengthsFromFront[j]) lengthsFromFront[i]=lengthsFromFront[j]+1; } } for(int i=sequence.length-1;i>=0;i--){ for(int j=i+1;j<sequence.length;j++){ if(sequence[j]<sequence[i] && lengthsFromBehind[i]<=lengthsFromBehind[j]) lengthsFromBehind[i]=lengthsFromBehind[j]+1; } } for(int i=0;i<sequence.length;i++){ if(lengthsFromFront[i]==1 || lengthsFromBehind[i]==1)continue; maxLength=Math.max(maxLength,lengthsFromFront[i]+lengthsFromBehind[i]-1); } return sequence.length-maxLength; } } C#
public class Solution { public int MinimumMountainRemovals(int[] sequence) { int [] lengthsFromFront= new int[sequence.Length]; int [] lengthsFromBehind= new int[sequence.Length]; int maxLength=1; for(int i=0;i<lengthsFromFront.Length;i++)lengthsFromFront[i]=1; for(int i=0;i<lengthsFromBehind.Length;i++)lengthsFromBehind[i]=1; for(int i=0;i<sequence.Length;i++){ for(int j=i-1;j>=0;j--){ if(sequence[j]<sequence[i] && lengthsFromFront[i]<=lengthsFromFront[j]) lengthsFromFront[i]=lengthsFromFront[j]+1; } } for(int i=sequence.Length-1;i>=0;i--){ for(int j=i+1;j<sequence.Length;j++){ if(sequence[j]<sequence[i] && lengthsFromBehind[i]<=lengthsFromBehind[j]) lengthsFromBehind[i]=lengthsFromBehind[j]+1; } } for(int i=0;i<sequence.Length;i++){ if(lengthsFromFront[i]==1 || lengthsFromBehind[i]==1)continue; maxLength=Math.Max(maxLength,lengthsFromFront[i]+lengthsFromBehind[i]-1); } return sequence.Length-maxLength; } } Javascript
var minimumMountainRemovals = function(sequence) { const lengthsFromFront= []; const lengthsFromBehind= []; lengthsFromFront.length=sequence.length; lengthsFromBehind.length=sequence.length; let maxLength=1; for(let i=0;i<lengthsFromFront.length;i++)lengthsFromFront[i]=1; for(let i=0;i<lengthsFromBehind.length;i++)lengthsFromBehind[i]=1; for(let i=0;i<sequence.length;i++){ for(let j=i-1;j>=0;j--){ if(sequence[j]<sequence[i] && lengthsFromFront[i]<=lengthsFromFront[j]) lengthsFromFront[i]=lengthsFromFront[j]+1; } } for(let i=sequence.length-1;i>=0;i--){ for(let j=i+1;j<sequence.length;j++){ if(sequence[j]<sequence[i] && lengthsFromBehind[i]<=lengthsFromBehind[j]) lengthsFromBehind[i]=lengthsFromBehind[j]+1; } } for(let i=0;i<sequence.length;i++){ if(lengthsFromFront[i]==1 || lengthsFromBehind[i]==1)continue; maxLength=Math.max(maxLength,lengthsFromFront[i]+lengthsFromBehind[i]-1); } return sequence.length-maxLength; }; C++
class Solution { public: int minimumMountainRemovals(vector<int>& sequence) { vector<int> lengthsFromFront; vector<int> lengthsFromBehind; int maxLength=1; for(int i=0;i<sequence.size();i++)lengthsFromFront.push_back(1); for(int i=0;i<sequence.size();i++)lengthsFromBehind.push_back(1); for(int i=0;i<sequence.size();i++){ for(int j=i-1;j>=0;j--){ if(sequence.at(j)<sequence.at(i) && lengthsFromFront.at(i)<=lengthsFromFront.at(j)) lengthsFromFront.at(i)=lengthsFromFront.at(j)+1; } } for(int i=sequence.size()-1;i>=0;i--){ for(int j=i+1;j<sequence.size();j++){ if(sequence.at(j)<sequence.at(i) && lengthsFromBehind.at(i)<=lengthsFromBehind.at(j)) lengthsFromBehind.at(i)=lengthsFromBehind.at(j)+1; } } for(int i=0;i<sequence.size();i++){ if(lengthsFromFront.at(i)==1 || lengthsFromBehind.at(i)==1)continue; maxLength=std::max(maxLength,lengthsFromFront.at(i)+lengthsFromBehind.at(i)-1); } return sequence.size()-maxLength; } }; 
