代码随想录打卡—day52—【子序列问题】— 8.31 最大子序列

共性

做完下面三题，发现三个的dp数组中i都是以 i 为结束的字串。

1 300. 最长递增子序列

300. 最长递增子序列

AC：

class Solution {
public:int dp[10010];  // 表示以i结束的子序列最大的长度/*if(nums[j] > nums[i])dp[j] = max(dp[j],dp[i] + 1);dp[0..nums.size()-1] = 1;每个i结束i++ ， j = 0...n-1 j++模拟——*/int lengthOfLIS(vector<int>& nums) {for(int i = 0; i < nums.size();i++)dp[i] = 1;int ans = 0;for(int i = 0; i < nums.size();i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i])dp[i] = max(dp[i],dp[j] + 1);}ans = max(ans,dp[i]);}return ans;}
};

2 674. 最长连续递增序列

674. 最长连续递增序列

和上一题差不多，就是 j 直接为 i - 1 即可。AC代码：

class Solution {
public:int dp[10010]; // 以i结束的子序列最长的连续递增的长度/*j = i-1if(nums[i] > nums[j])dp[i] = max(dp[i],dp[j])dp[0...n-1] = 1i++ j模拟——*/int findLengthOfLCIS(vector<int>& nums) {for(int i = 0; i < nums.size();i++)dp[i] = 1;int ans = 1;for(int i = 1; i < nums.size();i++){int j = i-1;if(nums[i] > nums[j])dp[i] = max(dp[i],dp[j]+1);ans = max(ans,dp[i]);cout << dp[i] << ' ';}return ans;}
};

前两题概括来说：

不连续递增子序列的跟前0-i 个状态有关，连续递增的子序列只跟前一个状态有关

3 718. 最长重复子数组

718. 最长重复子数组

重点：

1.

注意题目中说的子数组，暗指的是连续子序列。

2.

int dp[1010][1010]; // nums1以i结尾！ nums2的以j结尾！ 最长公共子串的长度

以x结尾两个字串才可比较。

3.

需要重点理解dp[i][j] 只能从dp[i-1][j-1]推导出来 不能从dp[i-1][j] 或是dp[i][j-1]

carl一共在实现细节上给了三种方式，我使用了dp数组含义更加直观但是多写几行的第三种写法（在拓展部分）AC代码：

class Solution {
public:int dp[1010][1010]; // nums1以i结尾！ nums2的以j结尾！ 最长公共子串的长度/*需要重点理解dp[i][j] 只能从dp[i-1][j-1]推导出来 不能从dp[i-1][j] 或是dp[i][j-1]if(nums[i] == nums[j])dp[i][j] = dp[i - 1][j - 1] + 1else dp[i][j] = 0for(int j = 0; j < nums1.size();j++)if(nums2[0] == nums1[i]) dp[0][j] = 1else dp[0][j] = 0for(int i = 0; i < nums2.size();i++)if(nums1[0] == nums2[i]) dp[i][0] = 1else dp[i][0] = 0;i++ j++*/int findLength(vector<int>& nums1, vector<int>& nums2) {int ans = 0;for(int j = 0; j < nums1.size();j++){if(nums2[0] == nums1[j]) dp[0][j] = 1;else dp[0][j] = 0;ans = max(ans,dp[0][j]);}for(int i = 0; i < nums2.size();i++){if(nums1[0] == nums2[i]) dp[i][0] = 1;else dp[i][0] = 0;ans = max(ans,dp[i][0]);}for(int i = 1; i < nums2.size();i++){for(int j = 1; j < nums1.size();j++){if(nums2[i] == nums1[j])dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = 0;ans = max(ans,dp[i][j]);}}// for(int i = 0; i < nums2.size();i++)// {//     for(int j = 0; j < nums1.size();j++)//         cout << dp[i][j] << ' ';//     cout << endl;// }return ans;}
};