一、最长递增子序列
300. 最长递增子序列 - 力扣（LeetCode）
前几天算法课上老师讲了
状态定义：
dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。
转移方程： 设 j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：
当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；
当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。
上述所有 1. 情况 下计算出的 dp[j]+1 的最大值，为直到 i 的最长上升子序列长度（即 dp[i] ）。实现方式为遍历 j 时，每轮执行 dp[i]=max(dp[i],dp[j]+1)。
转移方程： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)。
初始状态：
dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。
返回值：
返回 dp 列表最大值，即可得到全局最长上升子序列长度。
300. 最长递增子序列 - 力扣（LeetCode）
// Dynamic programming.
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0) return 0;
int[] dp = new int[nums.length];
int res = 0;
Arrays.fill(dp, 1);
for(int i = 0; i < nums.length; i++) {
for(int j = 0; j < i; j++) {
if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
res = Math.max(res, dp[i]);
}
return res;
}
}
二、最长连续递增序列
674. 最长连续递增序列 - 力扣（LeetCode）
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(nums.length <= 1)
return nums.length;
int ans = 1;
int count = 1;
for(int i=0;i<nums.length-1;i++) {
if(nums[i+1] > nums[i]) {
count++;
} else {
count = 1;
}
ans = count > ans ? count : ans;
}
return ans;
}
}
三、 最长重复子数组
class Solution {
public int findLength(int[] nums1, int[] nums2) {
return nums1.length<=nums2.length? findMax(nums1,nums2):findMax(nums2,nums1);
}
public int findMax(int[] nums1, int[] nums2){
int max=0;
int m=nums1.length,n=nums2.length;
/**
nums1,nums2中较短的数组不动，这里默认nums1，较长的数组滑动
初始位置：nums2右边界挨着nums1左边界，nums2从左往右滑动
*/
// 第一阶段：nums2从左往右滑动，两数组重合部分长度不断增加，重合部分长度len从1开始增加
// 重合部分：nums1起点下标0，nums2起点下标n-len，
for(int len=1;len<=m;len++){
max=Math.max(max,maxLen(nums1,0,nums2,n-len,len));
}
// 第二阶段：nums2从左往右滑动，两数组重合部分长度不变，重合部分长度始终为nums1长度m
// 重合部分：nums1起点下标0，nums2起点下标n-m，然后递减
for(int j=n-m;j>=0;j--){
max=Math.max(max,maxLen(nums1,0,nums2,j,m));
}
// 第三阶段：nums2从左往右滑动，两数组重合部分长度递减，重合部分长度始终为nums1长度m-i
// 重合部分：nums1起点下标i，递增，nums2起点下标0
for(int i=1;i<m;i++){
max=Math.max(max,maxLen(nums1,i,nums2,0,m-i));
}
return max;
}
/**
nums1中下标i开始，nums2中下标j开始，长度为len子数组中，最长公共子数组(注意要连续)长度
*/
public int maxLen(int[] nums1,int i,int[] nums2,int j,int len){
int count=0,res=0;
for(int k=0;k<len;k++){
if(nums1[i+k]==nums2[j+k]){
count++;
}else if(count>0){
//进入到这个if判断体里面，说明当前 nums1[i+k]!=nums2[j+k],即之前的公共子数组不再连续，
// 所以要记录最大值，同时将count置零
res=Math.max(count,res);
count=0;
}
}
/**
1，count>0,说明有公共子数组是以nums1[i+len-1],nums2[j+len-1]结尾的，
上面最后一步for循环没有进入到else if判断题里面，所以最终结果要取当前count和res的最大值
2，count=0，说明res已经更新过了，res即为最终结果
*/
return count>0? Math.max(count,res):res;
}
}
