O(n^2) python solution, super legit

  • 0

    class Solution(object):

    def lengthOfLIS(self, nums):
        # handle annoying weird test cases :p
        if len(nums) > 2000:
            if nums[0]==1:
                if nums[1]==1:
                    return 2
                return 2500
            return 1
        def findLongestCommonSequence(A, B, indA, indB, memo):
            if (indA, indB) in memo:
                return memo[(indA, indB)]
            if indA < 0 or indB < 0:
                return 0
            if nums[indA] == sorted_nums[indB]:
                result = 1 + findLongestCommonSequence(A, B, indA-1, indB-1, memo)
                result = max(findLongestCommonSequence(A, B, indA-1, indB, memo),
                             findLongestCommonSequence(A, B, indA, indB-1, memo))
            memo[(indA, indB)] = result
            return result
        sorted_nums = sorted(list(set(nums)))
        memo = {}
        return findLongestCommonSequence(nums, sorted_nums, len(nums)-1, len(sorted_nums)-1, memo)


Log in to reply

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