674. 最長連續(xù)遞增序列
給定一個未經(jīng)排序的整數(shù)數(shù)組，找到最長且 連續(xù)遞增的子序列，并返回該序列的長度。
連續(xù)遞增的子序列 可以由兩個下標(biāo) l 和 r（l < r）確定，如果對于每個 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續(xù)遞增子序列。
示例 1：
輸入：nums = [1,3,5,4,7]
輸出：3
解釋：最長連續(xù)遞增序列是 [1,3,5], 長度為3。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的，因?yàn)?5 和 7 在原數(shù)組里被 4 隔開。
示例 2：
輸入：nums = [2,2,2,2,2]
輸出：1
解釋：最長連續(xù)遞增序列是 [2], 長度為1。
1. 確定 dp 以及下標(biāo)的含義
dp[i]：以下標(biāo)i為結(jié)尾的數(shù)組的連續(xù)遞增的子序列長度為 dp[i]。
2. 確定遞推公式
如果 nums[i + 1] > nums[i]，那么以 i+1 為結(jié)尾的數(shù)組的連續(xù)遞增的子序列長度一定等于以i為結(jié)尾的數(shù)組的連續(xù)遞增的子序列長度 + 1 。
即：dp[i + 1] = dp[i] + 1
3. dp 數(shù)組初始化
以下標(biāo)i為結(jié)尾的數(shù)組的連續(xù)遞增的子序列長度最少也應(yīng)該是1，即就是nums[i]這一個元素。所以dp[i]應(yīng)該初始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. 最長遞增子序列
給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴(yán)格遞增子序列的長度。
子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [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 以及下標(biāo)的含義
dp[i] 表示i之前包括i的最長上升子序列。
2. 狀態(tài)轉(zhuǎn)移方程
位置 i 的最長升序子序列等于 j 從 0 到 i-1 各個位置的最長升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
這里不是要 dp[i] 與 dp[j] + 1進(jìn)行比較，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一個i，對應(yīng)的 dp[i]（即最長上升子序列）起始大小至少都是是1。
4. 確定遍歷順序
dp[i] 是有0到i-1各個位置的最長升序子序列推導(dǎo)而來，那么遍歷i一定是從前向后遍歷。
j其實(shí)就是0到i-1，遍歷i的循環(huán)里外層，遍歷j則在內(nèi)層，代碼如下：
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. 最長遞增子序列的個數(shù)
給定一個未排序的整數(shù)數(shù)組，找到最長遞增子序列的個數(shù)。
示例 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]; // 重置計數(shù)
} else if (dp[j] + 1 === dp[i]) {
cnt[i] += cnt[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i]; // 重置計數(shù)
} else if (dp[i] === maxLen) {
ans += cnt[i];
}
}
return ans;
};
1027. 最長等差數(shù)列
給定一個整數(shù)數(shù)組 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
解釋：
整個數(shù)組是公差為 3 的等差數(shù)列。
示例 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++) { // 中間的數(shù)字
for (let j = i + 1; j < len; j++) { // 后面的數(shù)字
for (let k = 0; k < i; k++) { // 前面的數(shù)字
if (nums[j] - nums[i] === nums[i] - nums[k]) { // 構(gòu)成等差數(shù)列
dp[i][j] = Math.max(dp[k][i] + 1, dp[i][j])
ans = Math.max(dp[i][j], ans)
}
}
}
}
return ans
};
334. 遞增的三元子序列
給你一個整數(shù)數(shù)組 nums ，判斷這個數(shù)組中是否存在長度為 3 的遞增子序列。
如果存在這樣的三元組下標(biāo) (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) 滿足題意，因?yàn)?nums[3] == 0 < nums[4] == 4 < nums[5] == 6
這道題是 300. 最長遞增子序列 變種過來的，思路差不多，只有處理一些小細(xì)節(jié)就可以了。當(dāng)然肯定有更加優(yōu)秀的解法，這里就留給讀者發(fā)揮了。
1. 確定 dp 以及下標(biāo)的含義
dp[i] 表示i之前包括i的最長上升子序列。
2. 狀態(tài)轉(zhuǎn)移方程
位置 i 的最長升序子序列等于 j 從 0 到 i-1 各個位置的最長升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
這里不是要 dp[i] 與 dp[j] + 1進(jìn)行比較，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一個i，對應(yīng)的 dp[i]（即最長上升子序列）起始大小至少都是是1。
4. 確定遍歷順序
dp[i] 是有0到i-1各個位置的最長升序子序列推導(dǎo)而來，那么遍歷i一定是從前向后遍歷。
j其實(shí)就是0到i-1，遍歷i的循環(huán)里外層，遍歷j則在內(nèi)層，代碼如下：
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. 最長數(shù)對鏈
給出 n 個數(shù)對。 在每一個數(shù)對中，第一個數(shù)字總是比第二個數(shù)字小。
現(xiàn)在，我們定義一種跟隨關(guān)系，當(dāng)且僅當(dāng) b < c 時，數(shù)對(c, d) 才可以跟在 (a, b) 后面。我們用這種形式來構(gòu)造一個數(shù)對鏈。
給定一個數(shù)對集合，找出能夠形成的最長數(shù)對鏈的長度。你不需要用到所有的數(shù)對，你可以以任何順序選擇其中的一些數(shù)對來構(gòu)造。
示例：
輸入：[[1,2], [2,3], [3,4]]
輸出：2
解釋：最長的數(shù)對鏈?zhǔn)?[1,2] -> [3,4]
這道題是 300. 最長遞增子序列 變種過來的，思路差不多，只有處理一些小細(xì)節(jié)就可以了。當(dāng)然肯定有更加優(yōu)秀的解法，這里就留給讀者發(fā)揮了。
先對 envelopes 進(jìn)行排序，之后進(jìn)行套模板就行了。
1. 確定 dp 以及下標(biāo)的含義
dp[i] 表示i之前包括i的最長上升子序列。
2. 狀態(tài)轉(zhuǎn)移方程
位置 i 的最長升序子序列等于 j 從 0 到 i-1 各個位置的最長升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
這里不是要 dp[i] 與 dp[j] + 1進(jìn)行比較，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一個i，對應(yīng)的 dp[i]（即最長上升子序列）起始大小至少都是是1。
4. 確定遍歷順序
dp[i] 是有0到i-1各個位置的最長升序子序列推導(dǎo)而來，那么遍歷i一定是從前向后遍歷。
j其實(shí)就是0到i-1，遍歷i的循環(huán)里外層，遍歷j則在內(nèi)層，代碼如下：
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. 俄羅斯套娃信封問題
給你一個二維整數(shù)數(shù)組 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 個信封的寬度和高度。
當(dāng)另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進(jìn)另一個信封里，如同俄羅斯套娃一樣。
請計算 最多能有多少個 信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面）。
注意：不允許旋轉(zhuǎn)信封。
示例 1：
輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出：3
解釋：最多信封的個數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。
示例 2：
輸入：envelopes = [[1,1],[1,1],[1,1]]
輸出：1
這道題是 300. 最長遞增子序列 變種過來的，思路差不多，只有處理一些小細(xì)節(jié)就可以了。當(dāng)然肯定有更加優(yōu)秀的解法，這里就留給讀者發(fā)揮了。
先對 envelopes 進(jìn)行排序，之后進(jìn)行套模板就行了。
1. 確定 dp 以及下標(biāo)的含義
dp[i] 表示i之前包括i的最長上升子序列。
2. 狀態(tài)轉(zhuǎn)移方程
位置 i 的最長升序子序列等于 j 從 0 到 i-1 各個位置的最長升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
這里不是要 dp[i] 與 dp[j] + 1進(jìn)行比較，而是要取dp[j] + 1的最大值。
3. dp[i] 的初始化
每一個i，對應(yīng)的 dp[i]（即最長上升子序列）起始大小至少都是是1。
4. 確定遍歷順序
dp[i] 是有0到i-1各個位置的最長升序子序列推導(dǎo)而來，那么遍歷i一定是從前向后遍歷。
j其實(shí)就是0到i-1，遍歷i的循環(huán)里外層，遍歷j則在內(nèi)層，代碼如下：
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;
};
