代码随想录算法训练营第五十二天| ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

300.最长递增子序列

看完题后的思路

dp[i] [0,i]子数组中,以nums[i]结尾的子序列的长度
dp[i]=dp[j]+1 j从i-1向0遍历,在所有nums[j]<nums[i]中dp[j]最大
初始化 dp[0]=1

代码

class Solution {public int lengthOfLIS(int[] nums) {if (nums.length==0){return 0;}int[] dp=new int[nums.length];dp[0]=1;for (int i = 1; i <nums.length ; i++) {int j = i-1;int max=-1;for (; j >=0 ; j--) {if (nums[j]<nums[i]&&dp[j]>max){dp[i]=dp[j]+1;max=dp[j];}} if (max==-1){dp[i]=1;}}int max=0;for (int i : dp) {max=Math.max(i,max);}return max;}
}

看完题解的改进

dp【i】=max（dp【i】，dp【j】+1） nums【j】<nums【i】

674. 最长连续递增序列

看完题后的思路

dp[i]=dp[i-1]+1 nums[i]>nums[i-1]
dp[i]=1 else

代码

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

718. 最长重复子数组

看完题后的思路

dp[i][j]: 包含以A[i]结尾与以B[j]结尾的公共序列的长度
dp[i][j]=dp[i-1][j-1]+1 A[i]=B[j] else =0
初始化
dp[0][j]= 0/1
dp[i][0]=0/1

代码

 public int findLength(int[] nums1, int[] nums2) {int m=nums1.length,n=nums2.length;int max=0;int[][] dp=new int[m][n];for (int i = 0; i <n ; i++) {if (nums1[0]==nums2[i]){dp[0][i]=1;}else {dp[0][i]=0;}max=Math.max(dp[0][i],max);}for (int i = 0; i <m ; i++) {if (nums2[0]==nums1[i]){dp[i][0]=1;}else {dp[i][0]=0;}max=Math.max(dp[i][0],max);}// 核心for (int i = 1; i <m ; i++) {for (int j = 1; j <n ; j++) {if (nums1[i]==nums2[j]){dp[i][j]=dp[i-1][j-1]+1;}else {dp[i][j]=0;}max=Math.max(dp[i][j],max);}}return max;}