Leetcode 300.最长上升子序列

Posted on |

300. 最长上升子序列

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

1
2
3
4
5
示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

方法

方法1：动态规划 $O(n^2)$

第一层循环来更新dp，第二个循环来遍历之前的数字且必须比当前小，不能等于
dp[i]表示以nums[i]上升序列的最后一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        if n==0:
            return 0

        # 初始化应该是1，因为每个数字本身就是一个长度为1的上升子序列
        r=[1]*n

        # 每加入一个数都要把这个数和之前所有的数比较一下
        for i in range(n):
            for j in range(i):
                if nums[i]>nums[j]:
                    r[i]=max(r[j]+1,r[i])

        # 并不是返回r最后一个值，而是要再比较一次
        return max(r)

参考资料