[LeetCode]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( nlog n) time complexity?

题目大意:

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

例如,

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

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

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

进一步思考:你可以将时间复杂度优化至O( nlog n)吗?

解题思路:

O(n^2)解法(运行时间1676ms) :

动态规划(Dynamic Programming)

状态转移方程:

dp[x] = max(dp[x], dp[y] + 1) 其中 y < x Python代码: class Solution(object):def lengthOfLIS(self, nums):""":type nums: List[int]:rtype: int"""size = len(nums)dp = [1] * sizefor 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) - 1while low <= high:mid = (low + high) / 2if dp[mid] >= nums[x]:high = mid - 1else:low = mid + 1if low >= len(dp):dp.append(nums[x])else:dp[low] = nums[x]return len(dp)



分享给朋友:
您可能感兴趣的文章:
随机阅读: