题目描述：

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?

题目大意：

给定一个未经排序的整数数组，寻找最长递增子序列的长度。

例如，

给定 [10, 9, 2, 5, 3, 7, 101, 18],

最长递增子序列是：[2, 3, 7, 101]，因而长度是4。注意可能存在不止一个LIS组合，只需要返回长度即可。

算法应该满足O(n^2)复杂度。

进一步思考：你可以将时间复杂度优化至O(n log n)吗？

解题思路：

O(n^2)解法（运行时间1676ms）：

动态规划（Dynamic Programming）

状态转移方程：

dp[x] = max(dp[x], dp[y] + 1) 其中 y < x 并且 nums[x] > nums[y]

Python代码：

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        size = len(nums)
        dp = [1] * size
        for x in range(size):
            for y in range(x):
                if nums[x] > nums[y]:
                    dp[x] = max(dp[x], dp[y] + 1)
        return max(dp) if dp else 0

O(n * log n)解法（运行时间44ms）：

维护一个单调序列

遍历nums数组，二分查找每一个数在单调序列中的位置，然后替换之。

Python代码：

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

 

本文链接：http://bookshadow.com/weblog/2015/11/03/leetcode-longest-increasing-subsequence/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码