Python: dp with O(n^2), binary search with O(nlogn)


  • 9
    S
    class Solution(object):
    #using dP
    def lengthOfLIS1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        dp = [1]*len(nums)
        for i in range (1, len(nums)):
            for j in range(i):
                if nums[i] >nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)
    #using binary search
    def lengthOfLIS(self, nums):
        def search(temp, left, right, target):
            if left == right:
                return left
            mid = left+(right-left)/2
            return search(temp, mid+1, right, target) if temp[mid]<target else search(temp, left, mid, target)
        temp = []
        for num in nums:
            pos = search(temp, 0, len(temp), num)
            if pos >=len(temp):
                temp.append(num)
            else:
                temp[pos]=num
        return len(temp)

Log in to reply
 

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