Minimum Number of Removals to Make Mountain

lcpy gen -n 1671   # by problem number
lcpy gen -s minimum_number_of_removals_to_make_mountain_array   # by problem name

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

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].

from bisect import bisect_left


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def minimum_mountain_removals(self, nums: list[int]) -> int:
        def lis_lengths(seq: list[int]) -> list[int]:
            tails: list[int] = []
            lengths: list[int] = []
            for x in seq:
                pos = bisect_left(tails, x)
                if pos == len(tails):
                    tails.append(x)
                else:
                    tails[pos] = x
                lengths.append(pos + 1)
            return lengths

        inc = lis_lengths(nums)
        dec = lis_lengths(nums[::-1])[::-1]

        best = 0
        for i in range(1, len(nums) - 1):
            if inc[i] >= 2 and dec[i] >= 2:
                best = max(best, inc[i] + dec[i] - 1)
        return len(nums) - best