Share my Python Solution beating 90.36% (Patience (greedy) & DP)


  • 0
    M

    Method1: Dynamic Programming O(n^2) 16.38%

    • I construct a list f, which store the LIS of each element.
    • At each element, I compare it with the former element to find the LIS.
    • With the spirit of DP, I can insure that if I know nums[i-1]'s LIS, I can know nums[i]'s LIS.
    class Solution(object):
        def lengthOfLIS(self, nums):
            if not nums or len(nums) == 1: return len(nums)
            f = [1] * len(nums)
    
            for i in xrange(1, len(nums)):
                for j in xrange(i):
                    if nums[i] > nums[j]:
                        f[i] = max(f[i], f[j] + 1)
    
            return max(f)
    

    Method2: Patience: Greedy Algorithm O(nlog(n)) 90.36%

    • I construct a list f, which stores piles of substring in decreasing order.
    • Since I would not find the LIS itself and just find the length of LIS, f only stores the last element (smallest one) of each pile.
    • In the iteration, if nuts[i] > f[-1], directly append nuts[i] to the end of f
    • else, we use binary search to find the position, which nuts[i] belongs to, and replace it with nuts[i].
    class Solution(object):
        def lengthOfLIS(self, nums):
            if not nums: return 0
            f = [nums[0]]
    
            for i in xrange(1, len(nums)):
                # If nums[i] > the end of f, append nums[i] to f. 
                if nums[i] > f[-1]: f.append(nums[i])
                else:
                    # binary search
                    begin, end = 0, len(f) 
                    while begin < end:
                        mid = (begin + end) / 2
                        if nums[i] == f[mid]:
                            begin = mid
                            break
                        if nums[i] > f[mid]:
                            begin = mid + 1
                        else: end = mid
                    f[begin] = nums[i]
            return len(f)
    

    Greedy using python bisect (more concise)

    import bisect
    class Solution(object):
        def lengthOfLIS(self, nums):
            if not nums: return 0
            f = [nums[0]]
    
            for i in xrange(1, len(nums)):
                if nums[i] > f[-1]: f.append(nums[i])
                else:
                    pos = bisect.bisect_left(f, nums[i])
                    f[pos] = nums[i]
            return len(f)
    

Log in to reply
 

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