文章目录

• 一、300.最长递增子序列
• 二、674. 最长连续递增序列
• 三、718. 最长重复子数组

一、300.最长递增子序列

注意的点：

1. 需要两层遍历。
2. 第一层遍历是计算以每一个字符为尾的字符串中的最长递增子序列。
3. 第二层遍历通过用当前字符与前边每一个字符比较，若大于就说明递增，在这个字符dp值的基础上+1，最后取一个最大值
4. 最重要的，要对整个dp数组再进行一次遍历，寻求总的最大值。

public class 最长递增子序列300 {public int lengthOfLIS(int[] nums) {//表示考虑i之前的数的话最大长度int[] dp = new int[nums.length];//单单一个数，就是1for (int i = 0; i < dp.length; i++) {dp[i] = 1;}int result = dp[0];//两层循环for (int i = 1; i < dp.length; i++) {for (int j = 0; j < i; j++) {//如果nums[i]大于nums[j]说明可以组成递增序列，则可以+1，同时比较与现在的dp[i]的大小if(nums[i] > nums[j])dp[i] = Math.max(dp[i], dp[j] + 1);}result = Math.max(result, dp[i]);}//踩坑：最后返回的不是最后一位，而是所有位置的最大值//return dp[dp.length-1];return result;}
}

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

注意的点：

1. 因为是求连续，所以比较简单
2. 要注意判断数组长度，若为1，则直接返回1

以下是代码部分：

public class 最长连续递增序列674 {public int findLengthOfLCIS(int[] nums) {//这里要初始化为1，否则 [1] 这个数据过不了int result = 1;for (int i = 0; i < nums.length - 1; i++) {int tmp = 1;while ( i < nums.length-1 && nums[i] < nums[i+1]){tmp++;i++;}result = Math.max(result, tmp);}return result;}
}

三、718. 最长重复子数组

注意的点：

1. 暴力解法的超时问题：总是比较多次两个字符串前半部分的字符。解决方法：先比较后边，在发现当前字符相同时，就在后边的基础上+1，否则给当前dp值置为0.
2. 初始化的时候，比较两个字符的最后一位，若相等置1，否则置0.
3. 最后，要对所有的dp值进行比较，取一个最大值。

以下是代码部分：

public class 最长重复子数组718 {//暴力破解 转 动态规划public int findLength(int[] nums1, int[] nums2) {int result = 0;//记录以i、j为首字母的字符串的最长重复int[][] dp = new int[nums1.length][nums2.length];//初始化for (int i = 0; i < nums1.length; i++) {if( nums1[i] == nums2[nums2.length-1]) {dp[i][nums2.length - 1] = 1;result = 1;}}for (int j = 0; j < nums2.length; j++) {if( nums1[nums1.length-1] == nums2[j]) {dp[nums1.length - 1][j] = 1;result = 1;}}//从后向前推到//踩坑：这里要从 -2 开始（而不是 -1）for (int i = nums1.length-2; i >= 0; i--) {for (int j = nums2.length-2; j >= 0; j--) {//注意，这里dp数组没有在更新是进行max比较，所以它存的是当前解，而不是局部最优解//如果相同，加上后边相同的就是总长度if(nums1[i] == nums2[j])dp[i][j] = dp[i+1][j+1] + 1;//如果不相同，直接置为0elsedp[i][j] = 0;result = Math.max(result, dp[i][j]);}}return result;}
}