300. 最长上升子序列 [medium]

https://leetcode-cn.com/problems/longest-increasing-subsequence/

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

示例:

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

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

通过次数156,810 | 提交次数346,592

First Try

2020-10-12

之前在牛客网遇到了类似的题目，要求的是指出最长的上升子序列，而不是只要求长度。当时求解出了长度，但不知道怎么恢复出最长子序列来。不过当时问题还在于动态规划的思路出现了错误，导致求解个长度也非常的繁琐。当时解法是选择了第idx元素之后，后面的数列能够拥有的最长长度，导致求解出总长度后还要减去当前idx元素的长度，并且还要考虑如果不选择idx元素，前一个元素idx - 1又是什么情况。写得非常变扭，虽然最后还是把长度正确求取出来了。

这回直接从正面出发，而且刚好提示里说了算法为O(n^2)，那么刚好两个循环，发现竟然很容易的解决了问题，并没有那么复杂。本来认为暴力法复杂度都到2^n去了，但其实只要考虑选择当前元素的时候，能够接上前面最长的子元素序列即可，而后面的元素不一定选择当前元素。因此每次选择元素的时候，都把前面可以选择的子序列遍历一遍，由于使用cache，其实一轮遍历也只是O(i)而已。

于是两轮遍历，问题直接搞定。为了不用最后把全员遍历一遍，实现把最大的float('inf')无限大元素插入到末尾，最终不管那个子序列肯定是要选择这个元素的，因此用最后这个元素的子序列来获取答案即可。

至于如果想要知道最终的子序列是哪几个元素，只要cache里保存的元素变成列表即可，一路记录选择的idx，也同时知道了长度。

如果没有动态规划的记录，纯靠心算，一下子就混乱了，没有了抓手。

因此整体的解法，有点类似贪心算法 + 动态规划。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        cache[i], 选取idx之后，当前位置最长长度
        """
        nums.append(float('inf'))
        cache = [1] * len(nums)  # 选择自身，初始值都有1
        for i in range(len(nums)):
            for j in range(0, i):
                if nums[j] < nums[i] and cache[j] + 1 > cache[i]:
                    cache[i] = cache[j] + 1 
        return cache[-1] - 1

执行用时：1156 ms, 在所有 Python3 提交中击败了62.34%的用户
内存消耗：13.3 MB, 在所有 Python3 提交中击败了94.46%

300. 最长上升子序列 [medium]​

First Try​

300. 最长上升子序列 [medium]

First Try