https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array

Solution 1: using LIS

The first idea when I saw this problem is to use already existing problem 300: Longest Increasing Subsequence (LIS), you can see my solutions with explanations here https://leetcode.com/problems/longest-increasing-subsequence/discuss/667975/Python-3-Lines-dp-with-binary-search-explained

So, the idea is the following: split our list into two parts, and find LIS for left part and also Longest Decreasing Subsequence for the second part. However we need to handle couple of things before: first of all, we want our LIS end with index i, so for this we can remove all elements which are less than nums[i] from our part. The same we do for the right part and we also reverse it. Finally, find LIS for these parts and if lengths of both parts 2 or more, it means we can construct Mountain Array, so we update our max_found.

Complexity: time complexity it is O(n log n) for one LIS, so it will be O(n^2 log n) for all partitions, space complexity is O(n).

class Solution:
    def minimumMountainRemovals(self, nums):
        def lengthOfLIS(nums):
            dp = [10**10] * (len(nums) + 1)
            for elem in nums: 
                dp[bisect.bisect_left(dp, elem)] = elem  
            return dp.index(10**10)

        max_found = 0
        n = len(nums)
        for i in range(1, n - 1):
            left  = [num for num in nums[:i] if num < nums[i]] + [nums[i]]
            right = [nums[i]] + [num for num in nums[i+1:] if num < nums[i]]
            right = right[::-1]
            a, b = lengthOfLIS(left), lengthOfLIS(right)
            if a >=2 and b >= 2: 
                max_found = max(max_found, a + b - 1)

        return n - max_found

Solution 2, using pure dp

Actually, it can be done in easier way: let dp1[i] be maximum length of LIS, ending with element index i and dp2[i] be maximum length of Mountain array. Then, update of dp1 is straightforward: iterate over all previous elements and update it. For dp2[i] we again need to iterate over all previous elements and if nums[j] < nums[i], we can update dp2[i], using dp2[j] + 1 or dp1[j] + 1.

Complexity: time complexity is O(n^2), space complexity is O(n).

class Solution:
    def minimumMountainRemovals(self, nums):
        n = len(nums)
        dp1, dp2 = [1]*n, [1]*n
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]: dp1[i] = max(dp1[i], 1+dp1[j])
                if nums[j] > nums[i]: 
                    if dp1[j] > 1: dp2[i] = max(dp2[i], 1 + dp1[j])
                    if dp2[j] > 1: dp2[i] = max(dp2[i], 1 + dp2[j])
        
        return n - max(dp2)

Solution 3, O(n log n)

Actually, we can update LIS solution we already have, but now we need to return also lens array, where lens[i] is the lenght of LIS, ending with index i.

class Solution:
    def minimumMountainRemovals(self, nums):
        def LIS(nums):
            dp = [10**10] * (len(nums) + 1)
            lens = [0]*len(nums)
            for i, elem in enumerate(nums): 
                lens[i] = bisect_left(dp, elem) + 1
                dp[lens[i] - 1] = elem 
            return lens
        
        l1, l2 = LIS(nums), LIS(nums[::-1])[::-1]
        ans, n = 0, len(nums)
        for i in range(n):
            if l1[i] >= 2 and l2[i] >= 2:
                ans = max(ans, l1[i] + l2[i] - 1)
                
        return n - ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 1671