image.png
问题描述
给定一个未排序的整数数组，找出最长的递增子序列。
栗子：
输入：[10,9,2,5,3,7,101,18]
输出：4
解释：
最长的递增子序列为：[2,3,7,101]，长度为 4.
注意：
- 可能存在多种最长递增子序列的组合，只需要返回其长度即可。
- 算法时间复杂度需要在
O(n2)之内。
解题思路
从上面的栗子，我们可以看出，递增子序列不要求连续。
开门见山，直接说下这道题的解法，即动态规划。使用动态规划的思想，在已有结果基础上，计算当前结果。
拿上述栗子举例，[10,9,2,5,3,7,101,18]，我们从后往前逐个分析。
为什么要从后往前呢？因为对于我来说这样看起来更直观。当然从前往后也是可行的，当你理解了思想后，可以尝试着从前往后再推导一遍。只不过有些许差别。
从后往前，记录的是以这个数开始的递增子序列的长度。
从前往后，记录的是以这个数结束的递增子序列的长度。
弄清楚上述差别后，再加上下面的逐步推导说明，相信如何从前往后分析你也能弄明白。
将 f(n) 记为从数字 n 开始的最大递增子序列长度。
-
18。从它开始的递增子序列只有它本身，那么f(18) = 1。 -
101。其后没有比它大的数字，那么从它开始的递增子序列也只有它自己，f(101) = 1。 -
7。101和18都比它大，那它跟谁组合在一起更长呢？很简单，只需取f(101)和f(18)中的最大值，再加上它自身的长度1，即f(7) = max(f(101), f(18)) + 1 = 2。 -
3。7、101、18比它大，同理，取三者中的最大值，再加上它本身，即f(3) = max(f(7), f(101), f(18)) + 1 = 3。 -
5。7、101、18比它大，同样需要取三者最大值，f(5) = max(f(7), f(101), f(18)) + 1 = 3。 -
2。5、3、7、101、18比它大，同样取这几个中的最大值，f(2) = max(f(5), f(3), f(7), f(101), f(18)) + 1 = 4。 -
9。101、18比它大，f(9) = max(f(101), f(18)) + 1 = 2。 -
10。101、18比它大，f(10) = max(f(101), f(18)) + 1 = 2。
不知从上面的推导过程中，你有没有发现一些规律？
当计算某个数字的最长递增子序列长度时，根据所有比其大的数字的结果，取出最大值，然后再加上它本身长度 1，即可得出结果。当然，也可能根本没有比大的数字，那么结果就是 1。
所以，解题思路总结如下：
- 对于某个数来说，如果其后没有比其大的数，那么长度为
1。 - 如果有比它大的数，那么取所有大于它的数的结果最大值，再加
1。用数学公式表示如下：// x/y/z 都大于 n f(n) = max(f(x), f(y), f(z), ...) + 1
在上述过程中，我们可以计算出以每个数字开始的最长递增子序列长度，那么整体的最长递增子序列长度也自然很好求出。
下面给出 js 代码实现，可以对照着看一下。
var lengthOfLIS = function (nums) {
if (nums && nums.length > 0) {
let result = 1;
// 保存已计算的长度
let lenList = [];
// 从后往前计算
let i = nums.length - 1;
while (i >= 0) {
// 同样从后往前计算比其大的最长递增序列长度
let j = nums.length - 1;
let maxLen = 0;
while (j > i) {
if (nums[j] > nums[i]) {
// 计算 index，最末尾是 0
const index = nums.length - 1 - j;
// 计算最大值
if (index >= 0 && index < lenList.length) {
maxLen = Math.max(maxLen, lenList[index]);
}
}
j -= 1;
}
maxLen += 1;
// 整体最大值
if (result < maxLen) {
result = maxLen;
}
lenList.push(maxLen);
i -= 1;
}
return result;
}
return 0;
};
