Python O(nlogn) and O(N^2) Solution


  • 0
    D

    O(N^2)

    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n = len(nums)
            if n == 0: return 0
            dp = [1]*n
            for i in range(n-1, -1, -1):
                for j in range(i+1, n):
                    if nums[j] > nums[i]:
                        dp[i] = max(dp[i], 1+dp[j])
            return max(dp)
    
    

    O(NlogN)

    from bisect import bisect_left
    class Solution(object):
        def lengthOfLIS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            ans = 0
            n = len(nums)
            if n == 0: return ans
            dp = [0]*n # minimal val for length i+1
            for x in nums:
                j = bisect_left(dp[:ans], x)
                dp[j] = x
                if j == ans: ans += 1
            return ans

Log in to reply
 

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