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

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

一、300.最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/
思路：定义dp[i]表示从0到i的闭区间的最长子序列长度。求任一个dp[i]都要用每一个数与该数比较。
dp[me] = max(dp[me], dp[j] + 1);

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 1) return 1;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

题目链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
思路：连续数组单层循环即可，只要不连续就又从1开始，连续就累加。

class Solution {
    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;
            }
            if (dp[i] > max) max = dp[i];
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、718. 最长重复子数组

题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
思路：依旧是从区间出发，定义dp[i][j]表示[0,i][0,j]区间中最长连续相等的子数组的长度。

class Solution {
     public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        int max = 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;
                if (dp[i][j]>max) max = dp[i][j];
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13