Longest Increasing Subsequence

Question

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Tags

• Array
• Dynamic Programming
• Binary Search

Thought

Three different solutions:

• DP with LCS
• DP
• DP and Binary Search (https://discuss.leetcode.com/topic/28738/java-python-binary-search-o-nlogn-time-with-explanation)

For the first algorithm, users can sort the array at first(remember to remove the duplicate item in the sorted array), then run Longest Comment Subsequence (LCS) between the original array and the sorted array.

For the second algorithm, users can build a DP array with 1 as the initialization. In any position in that DP array (let's take ith position as the example), it represents the length of the longest subsequence containing the ith element in the original array.

For the last algorithm, it needs to build DP array named tails with 0 as the initialization. In any position in that DP array (let's still take ith position as the example), it represents the smallest tail item in all the subsequence with length i + 1. It is easy to prove that this DP array should be an increasing array, so the binary search can be used for each item when traversing from the first item to the last item in the original array. For any item x in the loop:

(1) if x is larger than all tails, append it at the end of the tail, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

However, the efficiency of these three algorithms are totally different. The last algorithm is the fastest, then the second algorithm is much slower and the first algorithm is the slowest which cannot pass the time check in leetcode.

Code

DP with LCS

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sort_nums = list(set(nums))
        sort_nums.sort()   
        return self.lengthOfLCS(nums, sort_nums)

    def lengthOfLCS(self, nums1, nums2):
        """
        Use DP and memoization for LCS
        """
        DP = [[0 for i in xrange(len(nums2) + 1)] for j in xrange(len(nums1) + 1)]
        for i in xrange(1, len(nums1) + 1):
            for j in xrange(1, len(nums2) + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    DP[i][j] = DP[i - 1][j - 1] + 1
                else:
                    DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])
        return DP[-1][-1]

DP

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == []:
            return 0
        DP = [1 for _ in xrange(len(nums))]
        for i in xrange(1, len(nums)):
            maxDP = 0
            for j in xrange(i):
                if nums[j] >= nums[i]:
                    continue
                maxDP = max(maxDP, DP[j])
            DP[i] = maxDP + 1
        return max(DP)

Binary Search with DP

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tails = [0] * len(nums)
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i + j) / 2
                if tails[m] < x:
                    i = m + 1
                else:
                    j = m
            tails[i] = x
            size = max(i + 1, size)
        return size