[leetcode]300-最长上升子序列

来源：力扣 （LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例：

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

说明：

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

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

二、题解

首先要搞清楚的是题意：求最长上升子序列。子序列不是子串，两者的区别是子序列可以不连续，子串必须连续。

例如：[1, 3, 5, 2, 9]，最长上升子序列是 [1, 3, 5, 9]，最长上升子串是 [1, 3, 5] 。

2.1 暴力法

题目的一个要求是用 O(n^2) 的时间复杂度来完成这个问题，如果有 O(n^2) 的时间复杂度，可以直接使用暴力破解的办法：

算法的时间复杂度和空间复杂度都是 O(n^2) 。

2.2 动态规划

以dp[i]表示到第 i 个元素时的最大上升子序列长度，那么 dp[i] 就等于数组中上一个小于 nums[i] 的元素的最大上升子序列长度加 1 。这句话看起来比较难理解，可以通过下面的例子来理解。

以 [10,9,2,5,3,7] 为例，i=5 时如何求 dp[i]？此时 nums[i]=7，要想构造上升序列，它前面的数字都小于 7 才行。左边小于 7 的数字有三个：2 、 5 和 3 。

• 在数字 2 的地方，最大上升子序列的长度是 1，上升序列是 [2] 。
• 在数字 5 的地方，最大上升子序列的长度是 2，上升序列是 [2,5]；
• 在数字 3 的地方，最大上升子序列的长度是 2，上升序列是 [2,3] 。

因为 7 大于 3 个数字，所以到达 7 时，可以构造出来的上升序列有：[2,7], [2,5,7], [2,3,7]，这个时候最大的上升序列长度是 3，3 是从前面所有子序列的最大长度加 1 得到的。所以可以归纳出来的状态转移方程为：

$$dp[i]=max(dp[0], dp[1],..., dp[i-1])+1, n<i, nums[n]<=nums[i].​ $$ \( \)

使用动态规划的时间复杂度也是 O(n^2)，空间复杂度 O(n) 。

2.3 二分法求解

二分法不容易想出来，即使是看题解也是看了几遍才明白。

存在数组 tails，tails[i] 表示最大上升子序列长度为 i的子序列的末尾元素的最小值，这种情况下 tails 的长度就是最大子序列的长度。

以 [10, 9, 2, 5, 7] 为例解释 tails 数组每个元素的意义：

1. 长度为 1 的子序列有 5 个，每个元素都可以看作独立的子序列，其中最小的数字是 2，所以 tails[1]=2 。
2. 长度为 2 的子序列有 [2, 5], [2, 7] 和 [5, 7]，其中末尾数最小的是 5，所以 tails[2]=5 。
3. 长度为 3 的子序列只有 [2, 5, 7]，末尾数只有一个就是 7，所以 tails[3]=7 。

首先，暂且假设这个数组存在。然后结合 tails 数组的特性，可以确定的一个问题是 tails[i] 肯定大于 tails[i-1]，tails 数组一定严格递增。因为 tails 数组保存的是每个递增序列的最小值，整个序列还是维持递增的特性，所以序列右边的元素肯定大于左边的。

tails 数组的算法：

• 在数组中找到第一个大于 nums[i] 的元素，替换它。
• 如果找不到一个大于 nums[i] 的元素，插入到数组最后。

如何找到第一个大于 nums[i] 的元素？因为序列是有序的，所以最快的算法是二分查找，只要找到第一个大于等于它的值就可以了。时间复杂度为 O(nlogn)，空间复杂度为 O(n) 。

为什么一定要保存每个序列长度的最小值

一个要注意的问题是 tails[i] 表示的是长度为 i 的子序列的末尾元素的最小值，以 [1, 5, 3, 4] 为例，最大上升子序列长度为 2 的有两个：[1, 5] 和 [1, 3]，如果不取最小的末尾元素 3，那么 tails 数组就是 [1, 5]，当遍历到 4 的时候，找到第一个大于它的数是 5，此时下标等于 2，也就是说最大上升子序列长度就是 2 。而实际上应该是 3（子序列 [1, 3, 4]），结果不对。

三、代码

3.1 动态规划

3.2 二分法

通过二分法找到区间内第一个大于目标的元素：

求最长上升子序列：