代碼隨想錄算法訓練營Day51 | 300.最長遞增子序列 674. 最長連續遞增序列 718. 最長重復子數組
LeetCode 300.最長遞增子序列
題目鏈接：LeetCode 300.最長遞增子序列
思路：
選取最長子序列，并收集
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);dp[0] = 1;int result = 1;for(int i=1; i<n; i++){for(int j=0; j<i; j++){if(nums[i]>nums[j]) dp[i] = max(dp[i], dp[j]+1); }result = max(result, dp[i]);}return result;}
};
注意 ：
- 用max收集最長子序列
LeetCode 674. 最長連續遞增序列
題目鏈接：LeetCode 674. 最長連續遞增序列
思路：
記錄最大即可
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n,1);int result = 1;for(int i = 1; i < n; i++){for(int j=1; j<=i; j++){if(nums[j]>nums[j-1]) dp[j] = dp[j-1]+1;result = max(result, dp[j]);}}return result;}
};
注意 ：
1.
2.
3.
4.
LeetCode 718. 最長重復子數組
題目鏈接：LeetCode 718. 最長重復子數組
思路：
dp[i][j]的定義是i-1，j-1的最長重復子數組
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1));int result = 0;for(int i=1; i<=nums1.size(); i++){for(int j=1; j<=nums2.size(); j++){if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;result = max(dp[i][j], result);}}return result;}
};
注意 ：
- 判斷條件為i-1和j-1
)
