300.Longest Increasing Subsequence

Tags: [dp], [inner_loop_dp]

Link: https://leetcode.com/problems/longest-increasing-subsequence/#/description

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 is4. 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(nlogn) time complexity?

Solution: Inner Loop DP

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        # DP formula:
        # f[i] = max(f[j] + 1), 0<= j < i, nums[j] < nums[i].
        dp = [1 for _ in xrange(len(nums))]
        for i in xrange(1, len(nums)):
            for j in xrange(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

Revelation:

• See the comments in code.

Note:

• Time complexity = O(n^2), n is the number of elements of the given nums.

Follow Up:

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        increasing_subseq = []
        for n in nums:
            if not increasing_subseq or n > increasing_subseq[-1]:
                increasing_subseq.append(n)
            else:
                # try to find the index i at where increasing_subseq[i - 1] <= n <= increasing_subseq[i]
                index = self.binary_search(increasing_subseq, n)
                increasing_subseq[index] = n

        return len(increasing_subseq)

    def binary_search(self, arr, target):
        # find the index i at where arr[i - 1] <= target <= arr[i]
        start = 0
        end = len(arr) - 1

        while start <= end:
            mid = start + (end - start) / 2
            if target <= arr[mid]:
                if (mid - 1 < start) or (mid - 1 >= start and arr[mid - 1] <= target):
                    return mid
                end = mid - 1
            else:
                # n >= arr[mid]
                start = mid + 1

        return -1

Revelation:

• Try to build this longest increasing subsequence.
• If current num is greater than the last element of the increasing_subseq, so we just append the current num to end of the increasing_subseq.

• if current num less than greater than the last element of the increasing_subseq, we try to find a place i at where increasing_subseq[i - 1] <= current num <= increasing_subseq[i], then use the current num to update the increasing_subseq[i], which can make the increasing_subseq smaller and smaller.

• For example, the current num is 9, and current increasing_subseq = [3, 10], we find the i = 1, which make increasing[1 - 1] <= 9 <= increasing_subseq[1], so we use '9' to update the '10', after updating the increasing_subseq become to [3, 9].

• Another example, the current num is 3, and the current increasing_subseq = [1, 4, 10], after updating, the increasing_subseq become to [1, 3, 10], which give the future coming elements more 'space' to grow.
• Because when we build the increasing_subseq, we update the increasing_subseq based on the element's order, so the elements of the increasing_subseq is sorted. So we can apply binary search to find the position.

Note:

• Time complexity = O(nlgn), n is the number of elements in the given nums.