1 最长递增子序列

给你一个整数数组 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 <= nums.length <= 2500
• -104 <= nums[i] <= 104

思路：

我们使用动态规划的方法来解决这个问题，具体步骤如下：

1. 初始化：我们创建一个与原始数组长度相同的动态规划数组 dp，其中 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度，初始时都设为1。这是因为每个单独的元素都是一个长度为1的上升子序列。

2. 遍历：我们从数组的第二个元素开始，遍历整个数组。对于当前元素 nums[i]，我们再次从开头开始遍历到当前元素之前的所有元素 nums[j]。

3. 状态转移：

   位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

   所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

   如果 nums[i] 大于 nums[j]，说明 nums[i] 可以接在 nums[j] 后面形成一个更长的上升子序列。这时我们更新 dp[i] 为 dp[j] + 1 的最大值。这表示以 nums[i] 结尾的最长上升子序列的长度，取决于前面某个元素能够构成的最长上升子序列的长度加上当前元素。

4. 最大长度：在遍历过程中，我们始终保持一个变量 longest_length 来记录已经找到的最长上升子序列的长度。这个变量始终取 dp 数组中的最大值。

5. 结果返回：最终，遍历完成后 longest_length 就是整个数组的最长上升子序列的长度

代码：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {// 如果数组大小小于等于1，则直接返回数组大小，因为最长上升子序列最短也是1if (nums.size() <= 1) return nums.size();// 创建动态规划数组，初始值都为1，表示每个元素自身构成的最长上升子序列长度至少是1vector<int> dp(nums.size(), 1);// 用于存储最终的最长上升子序列的长度int longest_length = 1; // 最短的上升子序列长度是1，即单独一个元素// 遍历数组for (int i = 1; i < nums.size(); i++) {// 内层循环，遍历当前元素之前的元素for (int j = 0; j < i; j++) {// 如果当前元素 nums[i] 大于之前的某个元素 nums[j]，可以构成一个更长的上升子序列if (nums[i] > nums[j]) {// 更新 dp[i] 为 dp[j] + 1 的最大值，表示以当前元素 nums[i] 结尾的最长上升子序列长度dp[i] = max(dp[i], dp[j] + 1);}}// 更新最长上升子序列的长度，取当前 dp 数组中的最大值longest_length = max(longest_length, dp[i]);}// 返回最终的最长上升子序列长度return longest_length;}
};

2最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 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 <= nums.length <= 104
• -109 <= nums[i] <= 109

思路：

dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。

注意这里的定义，一定是以下标i为结尾，并不是说一定以下标0为起始位置。

1. 初始化：首先，我们需要明确最长连续递增子序列的概念，即在一个序列中找到最长的连续递增的子序列。为了解决这个问题，我们采用动态规划的方法。我们创建一个长度与原始数组相同的动态规划数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长连续递增子序列的长度。初始时，我们将所有的 dp[i] 都设为1。这是因为每个单独的元素都是一个连续递增子序列。

2. 遍历：接下来，我们从数组的第二个元素开始遍历整个数组。在遍历过程中，我们关注的是当前元素 nums[i] 与前一个元素 nums[i-1] 的关系。

3. 状态转移：如果 nums[i] 大于 nums[i-1]，说明 nums[i] 可以接在 nums[i-1] 后面形成一个更长的连续递增子序列。因此，我们将 dp[i] 更新为 dp[i-1] + 1。这表示以 nums[i] 结尾的最长连续递增子序列的长度取决于前面的某个元素能够构成的最长连续递增子序列的长度加上当前元素。

4. 最大长度：在遍历过程中，我们始终保持一个变量 result 来记录已经找到的最长连续递增子序列的长度。这个变量始终取 dp 数组中的最大值。

5. 结果返回：最终，遍历完成后，result 就是整个数组的最长连续递增子序列的长度。

代码：

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;  // 最短连续递增子序列的长度是1，即单独一个元素vector<int> dp(nums.size(), 1);  // 创建动态规划数组，初始值都为1，表示每个元素自身构成的最长连续递增子序列长度至少是1for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) {  // 如果当前元素大于前一个元素，说明可以构成连续递增子序列dp[i] = dp[i - 1] + 1;  // 更新 dp[i] 为 dp[i-1] + 1，表示以当前元素结尾的最长连续递增子序列长度}if (dp[i] > result) result = dp[i];  // 更新最长连续递增子序列的长度，取当前 dp 数组中的最大值}return result;  // 返回最终的最长连续递增子序列长度}
};

3 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

思路：

1. 创建一个二维动态规划数组 dp，其中 dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素形成的最长公共子数组的长度。
2. 初始化 dp 数组，将所有元素初始化为0。
3. 遍历 nums1 和 nums2 的每个元素，分别用 i 和 j 表示当前位置。
4. 如果 nums1[i - 1] 等于 nums2[j - 1]，说明当前位置的元素相等，那么更新 dp[i][j] = dp[i - 1][j - 1] + 1。
5. 在遍历过程中不断更新记录最长公共子数组长度的变量 result，如果 dp[i][j] 大于 result，则更新 result = dp[i][j]。
6. 最终返回 result，即为两个数组的最长公共子数组的长度。

代码：

// 版本一
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {// 创建二维动态规划数组，dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素形成的最长公共子数组的长度vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;  // 记录最长公共子数组的长度初始为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;  // 更新当前位置的最长公共子数组长度为前一个位置加1}if (dp[i][j] > result) result = dp[i][j];  // 更新最长公共子数组的长度}}return result;  // 返回最长公共子数组的长度}
};

4最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

思路：

1. 创建一个二维动态规划数组 dp，其中 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符形成的最长公共子序列的长度。
2. 初始化 dp 数组，将所有元素初始化为0。
3. 遍历 text1 和 text2 的每个字符，分别用 i 和 j 表示当前位置。
4. 如果 text1[i - 1] 等于 text2[j - 1]，说明当前位置的字符相等，那么更新 dp[i][j] = dp[i - 1][j - 1] + 1。
5. 如果不相等，取前一个位置的最长公共子序列长度的最大值，即 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。
6. 在遍历过程中不断更新记录最长公共子序列长度的值。
7. 最终返回 dp[text1.size()][text2.size()]，即为两个字符串的最长公共子序列长度。

代码：

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// 创建二维动态规划数组，dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符形成的最长公共子序列的长度vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));// 遍历两个字符串for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) {  // 如果当前字符相等dp[i][j] = dp[i - 1][j - 1] + 1;  // 更新当前位置的最长公共子序列长度为前一个位置加1} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  // 如果不相等，则取前一个位置的最长公共子序列长度的最大值}}}return dp[text1.size()][text2.size()];  // 返回 text1 和 text2 的最长公共子序列长度}
};