Leetcode 300-Longest Increasing Subsequence 题解

 

Leetcode 300-Longest Increasing Subsequence 题解题目Given an unsorted array of integers, find the length of longest increasing subsequence.Example:Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The...

Leetcode 300-Longest Increasing Subsequence 题解

题目

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

  • 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(n log n) time complexity?

分析

采用动态规划的思想,这里是第一种方法的时间复杂度。

设置一个dp数组,这个数组dp[i]保存着到位置i的最长递增字符串,最后返回dp里面最长的就是答案,其中dp[i]表示以nums[i]为结尾的最长递增子串的长度,对于每一个nums[i],我们从第一个数再搜索到i,如果发现某个数小于nums[i],我们更新dp[i],更新方法为dp[i] = max(dp[i], dp[j] + 1),即比较当前dp[i]的值和那个小于num[i]的数的dp值加1的大小,我们就这样不断的更新dp数组,到最后dp数组中最大的值就是我们要返回的LIS的长度。

这里最有趣的是更新的时候,是dp[i]=max(dp[i],dp[j] + 1) 这个地方,看到dp[j] + 1的意思就是说i这个位置的值比j的值大,那么这里就可以使用dp[j]+1来更新dp[i],这是重要的地方,选择这个和不选择这个的区别,是动态规划的常见问题,这里选择j就是要更新为dp[j]+1,不选择就还是dp[i],取最大,便是需要更新的地方。

代码

下面是AC的代码:

class Solution:
    def lengthOfLIS(self, nums):
        length = len(nums)
        dp = [1 for x in range(0, length)]
        for x in range(0, length):
            for y in range(0, x):
                if nums[x] > nums[y]:
                    dp[x] = max(dp[x], dp[y] + 1)
            maxlength = max(maxlength, dp[x])
        return maxlength

这个问题还有一个更快速的算法,能够优化时间到的时间复杂度,使用二分查找的方法来优化。

优化-耐心排序

先建立一个空的dp数组,这个数组的意义是到i时对应长度的最长递增数组序列中的最大长度,下面是为什么这样设置的原因:

比如一个数组:

1,3,5,2,8,6

当我们循环到6时,我们一共有如下4种不同长度递增序列,这些序列保证这个递增序列在相同长度的序列中末尾数字是最小的:

1

1,2

1,3,4

1,3,5,6

这些序列都是未来有机会能够增长到最长的,如果此时我们循环到一个新的数字,插入时会有3种情况:

  • 新的数字小于所有序列的末尾数字,则说明长度为1的序列可以更新改变数字为新加入的这个数字。
  • 新的数字大于所有序列的末尾数字,则说明可以新建一个新的最长序列了,也就是在最后一个序列的基础上,增加这个新的数字,成为一个新的序列。
  • 新的数字位于中间位置,则将其补充到最大的小于它的序列上面去。

下面是例子:

插入9,最大位置:

1

1,2

1,3,4

1,3,5,6

1,3,5,6,9

再插入3,中间位置:

1

1,2

1,3,3

13,5,6

如果插入0,最末位置:

0

1,2

1,3,3

13,5,6

最大和最小都很好解决,但是中间位置的寻找,就需要用二分查找的操作来寻找。

下面是AC的代码:

class Solution:
    def lengthOfLIS(self, nums):
        dp = []
        length = len(nums)
        for i in range(0, length):
            left = 0
            right = len(dp)
            while left < right:
                mid = left + (right - left) // 2
                if dp[mid] < nums[i]:
                    left = mid + 1
                else:
                    right = mid
            if right >= len(dp):
                dp.append(nums[i])
            else:
                dp[right] = nums[i]
        return len(dp)

感谢这篇博文,本文主要参考这篇博文,该博文中的代码写的很清晰。