前言

代码随想录算法训练营day52

一、Leetcode 300.最长递增子序列

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. 1 <= nums.length <= 2500
2. -104 <= nums[i] <= 104

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/longest-increasing-subsequence

2.解题思路

方法一：动态规划

思路与算法

定义 dp[i]dp[i] 为考虑前 ii 个元素，以第 ii 个数字结尾的最长上升子序列的长度，注意 nums[i]nums[i] 必须被选取。

我们从小到大计算 dpdp 数组的值，在计算 dp[i]dp[i] 之前，我们已经计算出 dp[0…i−1]dp[0…i−1] 的值，则状态转移方程为：

dp[i]=max⁡(dp[j])+1,其中 0≤j

即考虑往 dp[0…i−1]dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]nums[i]。由于 dp[j]dp[j] 代表 nums[0…j]nums[0…j] 中以 nums[j]nums[j] 结尾的最长上升子序列，所以如果能从 dp[j]dp[j] 这个状态转移过来，那么 nums[i]nums[i] 必然要大于 nums[j]nums[j]，才能将 nums[i]nums[i] 放在 nums[j]nums[j] 后面以形成更长的上升子序列。

最后，整个数组的最长上升子序列即所有 dp[i]dp[i] 中的最大值。

LISlength=max⁡(dp[i]),其中 0≤i

3.代码实现
```java class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int maxans = 1; for (int i = 1; i < nums.length; i++) { dp[i] = 1; for (int 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; } }
```

二、Leetcode 674. 最长连续递增序列

1.题目

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

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

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence

2.解题思路

方法一：贪心

对于下标范围 [l,r][l,r] 的连续子序列，如果对任意 l≤i

假设数组 numsnums 的长度是 nn，对于 0

1. 如果 nums[l−1]<nums[l]nums[l−1]<nums[l]，则将 nums[l−1]nums[l−1] 加到 nums[l]nums[l] 的前面，可以得到更长的连续递增序列.
2. 
3. 如果 nums[r+1]>nums[r]nums[r+1]>nums[r]，则将 nums[r+1]nums[r+1] 加到 nums[r]nums[r] 的后面，可以得到更长的连续递增序列。

基于上述分析可知，为了得到最长连续递增序列，可以使用贪心的策略得到尽可能长的连续递增序列。做法是使用记录当前连续递增序列的开始下标和结束下标，遍历数组的过程中每次比较相邻元素，根据相邻元素的大小关系决定是否需要更新连续递增序列的开始下标。

具体而言，令 startstart 表示连续递增序列的开始下标，初始时 start=0start=0，然后遍历数组 numsnums，进行如下操作。

1. 如果下标 i>0i>0 且 nums[i]≤nums[i−1]nums[i]≤nums[i−1]，则说明当前元素小于或等于上一个元素，因此 nums[i−1]nums[i−1] 和 nums[i]nums[i] 不可能属于同一个连续递增序列，必须从下标 ii 处开始一个新的连续递增序列，因此令 start=istart=i。如果下标 i=0i=0 或 nums[i]>nums[i−1]nums[i]>nums[i−1]，则不更新 startstart 的值。
2. 
3. 此时下标范围 [start,i][start,i] 的连续子序列是递增序列，其长度为 i−start+1i−start+1，使用当前连续递增序列的长度更新最长连续递增序列的长度。

遍历结束之后，即可得到整个数组的最长连续递增序列的长度。

3.代码实现

```java class Solution { public int findLengthOfLCIS(int[] nums) { int ans = 0; int n = nums.length; int start = 0; for (int i = 0; i < n; i++) { if (i > 0 && nums[i] <= nums[i - 1]) { start = i; } ans = Math.max(ans, i - start + 1); } return ans; } }
```

三、Leetcode 718. 最长重复子数组

1.题目

给两个整数数组 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. 1 <= nums1.length, nums2.length <= 1000
2. 0 <= nums1[i], nums2[i] <= 100

2.解题思路

方法一：动态规划

思路及算法

暴力解法的过程中，我们发现最坏情况下对于任意 i 与 j ，A[i] 与 B[j] 比较了 min⁡(i+1,j+1)min(i+1,j+1) 次。这也是导致了该暴力解法时间复杂度过高的根本原因。

不妨设 A 数组为 [1, 2, 3]，B 两数组为为 [1, 2, 4] ，那么在暴力解法中 A[2] 与 B[2] 被比较了三次。这三次比较分别是我们计算 A[0:] 与 B[0:] 最长公共前缀、 A[1:] 与 B[1:] 最长公共前缀以及 A[2:] 与 B[2:] 最长公共前缀时产生的。

我们希望优化这一过程，使得任意一对 A[i] 和 B[j] 都只被比较一次。这样我们自然而然想到利用这一次的比较结果。如果 A[i] == B[j]，那么我们知道 A[i:] 与 B[j:] 的最长公共前缀为 A[i + 1:] 与 B[j + 1:] 的最长公共前缀的长度加一，否则我们知道 A[i:] 与 B[j:] 的最长公共前缀为零。

这样我们就可以提出动态规划的解法：令 dp[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀，那么答案即为所有 dp[i][j] 中的最大值。如果 A[i] == B[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1，否则 dp[i][j] = 0。

这里借用了 Python 表示数组的方法，A[i:] 表示数组 A 中索引 i 到数组末尾的范围对应的子数组。

考虑到这里 dp[i][j] 的值从 dp[i + 1][j + 1] 转移得到，所以我们需要倒过来，首先计算 dp[len(A) - 1][len(B) - 1]，最后计算 dp[0][0]。

3.代码实现

```java class Solution { public int findLength(int[] A, int[] B) { int n = A.length, m = B.length; int[][] dp = new int[n + 1][m + 1]; int ans = 0; for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0; ans = Math.max(ans, dp[i][j]); } } return ans; } }
```