[来源] 🔗300. 最长递增子序列
题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
1
2
3
| 输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
|
示例 2：
1
2
| 输入：nums = [0,1,0,3,2,3]
输出：4
|
示例 3：
1
2
| 输入：nums = [7,7,7,7,7,7,7]
输出：1
|
思路一
- 首先我们先考虑直接的动态规划，初始化dp数组为new Array(len).fill(1)。
- 用1填充的原因是因为任意一个数字都可以组成一个长度，所以最短初始值为1。
- 那么现在我们的数组将是如下情况
1
2
3
4
|
nums = [10,9,2,5,3,7,101,18]
dp = [1, 1,1,1,1,1,1, 1 ]
|
- 计算最长递增子序列肯定要遍历数组的，而且
3.1. 计算最长，我们肯定要使用到Math.max；
3.2. 比较前后两个数的大小，我们先姑且的使用两层for循环吧 简单而粗暴
1
2
3
4
5
6
7
8
9
10
11
12
| 1. i = 1, j = 0
nums[i] < nums[j] continue;
2. i = 2, j from 0
2.1 j = 0
nums[i] < nums[j] continue; dp = [1, 1, ..., 1]
2.2 j = 1
nums[i] < nums[j] continue; dp = [1, 1, ..., 1]
3. i = 3, j from 0
3.1 3.2 如上 dp = [1, 1, ..., 1]
3.3 j = 2
nums[i] > nums[j] dp[i] = Math.max(dp[j] + 1, dp[i]); dp = [1, 1, 1, 2, ...1]
以此类推....
|
代码一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function lengthOfLIS(nums: number[]): number {
const len = nums.length;
const dp = new Array(len).fill(1);
let ans = 1;
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[j] + 1, dp[i])
}
}
ans = Math.max(dp[i], ans)
}
return ans;
};
|