文章目录
- 300.最长递增子序列
- 674. 最长连续递增序列
- 718. 最长重复子数组
300.最长递增子序列
想清楚如何推导dp数组是关键
两层for循环,因为递增序列不是连续的
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int result = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
result = Math.max(result, dp[i]);
}
return result;
}
674. 最长连续递增序列
不连续递增子序列的跟前0-i
个状态有关,连续递增的子序列只跟前一个状态有关
public int findLengthOfLCIS(int[] nums) {
if(nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int result = 1;
for (int i = 1; i < dp.length; i++) {
if(nums[i] > nums[i - 1]){
dp[i] = Math.max(dp[i], dp[i - 1] + 1);
}
if(result < dp[i]){
result = Math.max(result, dp[i]);
}
}
return result;
}
718. 最长重复子数组
-
暴力解法:只需要先两层for循环确定两个数组起始位置
,然后再来一个循环可以是for或者while,来从两个起始位置开始比较,取得重复子数组的长度
-
本题动态规划就是记录下暴力解法的所有可能性结果下,以某下表结尾的连续子数组的最大长度。记忆状态换时间
public int findLength(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 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;
result = Math.max(result, dp[i][j]);
}
}
}
return result;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)