674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
1. 确定 dp 以及下标的含义
dp[i]：以下标i为结尾的数组的连续递增的子序列长度为 dp[i]。
2. 确定递推公式
如果 nums[i + 1] > nums[i]，那么以 i+1 为结尾的数组的连续递增的子序列长度一定等于以i为结尾的数组的连续递增的子序列长度 + 1 。
即：dp[i + 1] = dp[i] + 1
3. dp 数组初始化
以下标i为结尾的数组的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。所以dp[i]应该初始1。
4. 确定遍历顺序
从递推公式上可以看出， dp[i + 1] 依赖 dp[i]，所以一定是从前向后遍历。
for (let i = 1; i < nums.length; i++) {
if (nums[i - 1] < nums[i]) {
dp[i] = dp[i - 1] + 1
}
}
完整代码
let findLengthOfLCIS = function (nums) {
if (nums.length === 1) return 1
let dp = new Array(nums.length)
let max = 0
dp[0] = 1
for (let i = 1; i < nums.length; i++) {
if (nums[i - 1] < nums[i]) {
dp[i] = dp[i - 1] + 1
} else {
dp[i] = 1
}
max = Math.max(max, dp[i])
}
return max
}
300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
1. 确定 dp 以及下标的含义
dp[i] 表示i之前包括i的最长上升子序列。
2. 状态转移方程
位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
这里不是要 dp[i] 与 dp[j] + 1进行比较，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一个i，对应的 dp[i]（即最长上升子序列）起始大小至少都是是1。
4. 确定遍历顺序
dp[i] 是有0到i-1各个位置的最长升序子序列推导而来，那么遍历i一定是从前向后遍历。
j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
完整代码
var lengthOfLIS = function (nums) {
if (nums.length == 0) {
return 0
}
let dp = new Array(nums.length)
dp[0] = 1
let maxans = 1
for (let i = 1; i < nums.length; i++) {
dp[i] = 1
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
maxans = Math.max(maxans, dp[i])
}
return maxans
};
673. 最长递增子序列的个数
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
完整代码
var findNumberOfLIS = function (nums) {
let n = nums.length, maxLen = 0, ans = 0;
const dp = new Array(n).fill(0);
const cnt = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
dp[i] = 1;
cnt[i] = 1;
for (let j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j]; // 重置计数
} else if (dp[j] + 1 === dp[i]) {
cnt[i] += cnt[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i]; // 重置计数
} else if (dp[i] === maxLen) {
ans += cnt[i];
}
}
return ans;
};
1027. 最长等差数列
给定一个整数数组 A，返回 A 中最长等差子序列的长度。
回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。
示例 1：
输入：[3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。
示例 2：
输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：
输入：[20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。
var longestArithSeqLength = function(nums) {
const len = nums.length
const dp = Array.from({ length: len }, () => new Array(len).fill(2))
let ans = 2
for (let i = 1; i < len; i++) { // 中间的数字
for (let j = i + 1; j < len; j++) { // 后面的数字
for (let k = 0; k < i; k++) { // 前面的数字
if (nums[j] - nums[i] === nums[i] - nums[k]) { // 构成等差数列
dp[i][j] = Math.max(dp[k][i] + 1, dp[i][j])
ans = Math.max(dp[i][j], ans)
}
}
}
}
return ans
};
334. 递增的三元子序列
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
这道题是 300. 最长递增子序列 变种过来的，思路差不多，只有处理一些小细节就可以了。当然肯定有更加优秀的解法，这里就留给读者发挥了。
1. 确定 dp 以及下标的含义
dp[i] 表示i之前包括i的最长上升子序列。
2. 状态转移方程
位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
这里不是要 dp[i] 与 dp[j] + 1进行比较，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一个i，对应的 dp[i]（即最长上升子序列）起始大小至少都是是1。
4. 确定遍历顺序
dp[i] 是有0到i-1各个位置的最长升序子序列推导而来，那么遍历i一定是从前向后遍历。
j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
完整代码
var increasingTriplet = function (nums) {
if (nums.length == 0) {
return 0
}
if (Array.from(new Set(nums)).length === 2) {
return false
}
let dp = new Array(nums.length)
dp[0] = 1
let maxans = 1
for (let i = 1; i < nums.length; i++) {
dp[i] = 1
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
maxans = Math.max(maxans, dp[i])
if (maxans >= 3) {
return true
}
}
return false
};
646. 最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
这道题是 300. 最长递增子序列 变种过来的，思路差不多，只有处理一些小细节就可以了。当然肯定有更加优秀的解法，这里就留给读者发挥了。
先对 envelopes 进行排序，之后进行套模板就行了。
1. 确定 dp 以及下标的含义
dp[i] 表示i之前包括i的最长上升子序列。
2. 状态转移方程
位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
这里不是要 dp[i] 与 dp[j] + 1进行比较，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一个i，对应的 dp[i]（即最长上升子序列）起始大小至少都是是1。
4. 确定遍历顺序
dp[i] 是有0到i-1各个位置的最长升序子序列推导而来，那么遍历i一定是从前向后遍历。
j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (envelopes[i][0] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
完整代码
var findLongestChain = function (envelopes) {
let n = envelopes.length;
if (n < 1) return 0;
let max = 1;
let dp = new Array(n).fill(1);
dp[0] = 1;
envelopes.sort((a, b) => a[0] - b[0])
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (envelopes[i][0] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
max = Math.max(max, dp[i]);
}
return max;
};
354. 俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
这道题是 300. 最长递增子序列 变种过来的，思路差不多，只有处理一些小细节就可以了。当然肯定有更加优秀的解法，这里就留给读者发挥了。
先对 envelopes 进行排序，之后进行套模板就行了。
1. 确定 dp 以及下标的含义
dp[i] 表示i之前包括i的最长上升子序列。
2. 状态转移方程
位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
这里不是要 dp[i] 与 dp[j] + 1进行比较，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一个i，对应的 dp[i]（即最长上升子序列）起始大小至少都是是1。
4. 确定遍历顺序
dp[i] 是有0到i-1各个位置的最长升序子序列推导而来，那么遍历i一定是从前向后遍历。
j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
完整代码
var maxEnvelopes = function (envelopes) {
let n = envelopes.length;
if (n < 1) return 0;
let max = 1;
let dp = new Array(n).fill(1);
dp[0] = 1;
envelopes.sort((a, b) => a[0] - b[0])
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
max = Math.max(max, dp[i]);
}
return max;
};
