代码随想录day43：动态规划part11，子序列问题

本文主要是介绍代码随想录day43：动态规划part11，子序列问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- day43：动态规划part11，子序列问题
- - 300.最长递增子序列
  - 674.最长连续递增序列
  - 718.最长重复子数组

day43：动态规划part11，子序列问题

300.最长递增子序列

class Solution {public int lengthOfLIS(int[] nums) {// dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度int n = nums.length;if (n == 1) return 1;int[] dp = new int[n];Arrays.fill(dp, 1);int ans = 0;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++)if (nums[i] > nums[j])dp[i] = Math.max(dp[i], dp[j] + 1);ans = Math.max(ans, dp[i]);}return ans;}
}

674.最长连续递增序列

class Solution {public int findLengthOfLCIS(int[] nums) {int n = nums.length;if (n == 1) return 1;int[] dp = new int[n];Arrays.fill(dp, 1);int ans = 0;for (int i = 1; i < n; i++) {if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;ans = Math.max(ans, dp[i]);}return ans;}
}

718.最长重复子数组

dp数组定义 i-1 j-1 是为了省略初始化，如果定义为以 i j 结尾需要对 dp[0] 的情况初始化

class Solution {public int findLength(int[] nums1, int[] nums2) {
// dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，
// 最长重复子数组长度为dp[i][j]。int[][] dp = new int[nums1.length + 1][nums2.length + 1];int ans = 0;for (int i = 1; i <= nums1.length; i++) {for (int j = 1; j <= nums2.length; j++) {if (nums1[i - 1] == nums2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;ans = Math.max(ans, dp[i][j]);}}return ans;}
}