Python BS O(nlogn), easy with bisect, very concise and clear


  • 0

    Using l to maintain the current length of dp to avoid using len() each time.

        def lengthOfLIS(self, nums):
            dp = []
            l = 0
            for num in nums:
                idx = bisect.bisect_left(dp, num) # find the insert position of num
                if idx < l: # num is smaller than some number in dp
                    dp[idx] = num
                else: # num is larger than any number in dp
                    dp.append(num)
                    l += 1
            return l
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.