BinarySearch 0467 Longest Bitonic Subsequence

Problem statement

https://binarysearch.com/problems/Longest-Bitonic-Subsequence/

Solution

Equal to Leetcode 1671. Minimum Number of Removals to Make Mountain Array.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(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
        
        nums = [-1] + nums + [-1]
        l1, l2 = LIS(nums), LIS(nums[::-1])[::-1]
        ans, n = 0, len(nums)
        for i in range(n):
            ans = max(ans, l1[i] + l2[i] - 1)
                
        return ans - 2