Longest Increasing Subsequence

Question Decription

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(n^2) complexity.

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

Solution

There are two ways to solve this question. One straight forward way is to use dynamic programming to do that. For any element in the array, it's easy to get:

$$dp[y] = max(dp[x] + 1, dp[y])$$

For the x, y satisfying x < y and index of y is larger than index of x. It is an O(n^2) solution.

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp, result = [1 for x in range(len(nums))], 1
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    result = max(dp[i], result)
        return result

But this solution cannot pass the big data test of leetcode. For an O(n^2) solution I just do not think this test makes sense. Too strict for python?

Then we have to do that in O(n logn). This one is hard to figure out.

We take the given example for analysis. We try to add the numbers in nums one by one to a increasing list.

1. empty list, so we just add 10. ----- [10]
2. 9 is smaller than 10, so we find the position to insert 9 is 0. ----- [9]
3. [2]
4. [2,5]
5. [2,3]
6. [2,3,7]
7. [2,3,7,101]
8. [2,3,7,18]

Then we get the longest increasing length is 4. Because we search the insert position to keep the increasing pattern, the final length of dp we get at last should be the result.

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = []
        for i in range(len(nums)):
            low, high = -1, len(dp)
            while low + 1 < high:
                mid = (high - low) / 2 + low
                if dp[mid] >= nums[i]:
                    high = mid
                else:
                    low = mid
            if high >= len(dp):
                dp.append(nums[i])
            else:
                dp[high] = nums[i]
        return len(dp)