Both O(n^2) and O(nlog(n)) solution


  • 0

    O(n^2) solution uses DP. Assume dp[i] is the LIS that ends up with nums[i], then dp[i] = max(dp[0..i-1]) + 1.

    class Solution(object):
        def lengthOfLIS(self, nums):
            dp = [1] * len(nums)
            for i in xrange(1, len(nums)):
                dp[i] = max([
                    dp[j] for j in xrange(i - 1, -1, -1) if nums[i] > nums[j]
                ] or [0]) + 1
            return max(dp or [0])
    

    O(nlog(n)) solution uses binary search. We maintain an increasing array making itself as long and its elements as small as possible.

    class Solution(object):
        def lengthOfLIS(self, nums):
            lis = []
            for num in nums:
                i = bisect.bisect_left(lis, num)
                if i >= len(lis):
                    lis.append(num)
                else:
                    lis[i] = num
            return len(lis)

Log in to reply
 

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