Longest Increasing Subsequence

题目描述

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?

解题方法

DP O(n^2)

一开始我想用dp[i]来表示在[:i+1]里面的最长LIS, 但是这样很难就要像global, lobal一样建两个array, local用来表示以i为终点的LIS的长度，这样最后只要找出array中的最大值就可以了.

function

for k in range(0, i):
    if nums[i] > nums[k] and dp[i] < dp[k] + 1:
        dp[i] = dp[k] + 1

这种方法对于每个i都要遍历0~i-1， 所以需要O(n^2)的复杂度

二分法

实际上，在对于i往前查找的过程中，只要比较nums[i]和之前LIS的最小结尾就可以， 比如

               0  1  2  3  4  5  6  7
nums[]:   2  5  6  2  3  4  7  4
dp[]:        1  2  3  1  2  3  4  3

对于nums[6], 前面最大的LIS长度为3，并且有两个，但是我们只需要比较小的那个结尾，就可以确定 nums[6]是否可以接到后面。 如果不行的话，就再找小1个长度的LIS的最小结尾比较。

所以我们要建一个新的array, last_min, last_min[i]表示目前长度为i的LIS的最小结尾。 并且用一个variable curMax记录目前最长的LIS， 这样便于比较。 而在查找这个i的过程可以使用二分法， 所以时间复杂度可以降到O(nlogn)

Solution

O(n^2)

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

        dp = [1 for i in range(len(nums))]
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1

        return max(dp)

O(nlogn)

Reference