day52|300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

一、300.最长递增子序列

注意的点：

1. 需要两层遍历。
2. 第一层遍历是计算以每一个字符为尾的字符串中的最长递增子序列。
3. 第二层遍历通过用当前字符与前边每一个字符比较，若大于就说明递增，在这个字符dp值的基础上+1，最后取一个最大值
4. 最重要的，要对整个dp数组再进行一次遍历，寻求总的最大值。

public class 最长递增子序列300 {

    public int lengthOfLIS(int[] nums) {

        //表示考虑i之前的数的话最大长度
        int[] dp = new int[nums.length];

        //单单一个数，就是1
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }

        int result = dp[0];

        //两层循环
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {

                //如果nums[i]大于nums[j]说明可以组成递增序列，则可以+1，同时比较与现在的dp[i]的大小
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            result = Math.max(result, dp[i]);
        }

        //踩坑：最后返回的不是最后一位，而是所有位置的最大值
        //return dp[dp.length-1];

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

注意的点：

1. 因为是求连续，所以比较简单
2. 要注意判断数组长度，若为1，则直接返回1

以下是代码部分：

public class 最长连续递增序列674 {

    public int findLengthOfLCIS(int[] nums) {

        //这里要初始化为1，否则 [1] 这个数据过不了
        int result = 1;

        for (int i = 0; i < nums.length - 1; i++) {
            int tmp = 1;
            while ( i < nums.length-1 && nums[i] < nums[i+1]){
                tmp++;
                i++;
            }

            result = Math.max(result, tmp);
        }

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、718. 最长重复子数组

注意的点：

1. 暴力解法的超时问题：总是比较多次两个字符串前半部分的字符。解决方法：先比较后边，在发现当前字符相同时，就在后边的基础上+1，否则给当前dp值置为0.
2. 初始化的时候，比较两个字符的最后一位，若相等置1，否则置0.
3. 最后，要对所有的dp值进行比较，取一个最大值。

以下是代码部分：

public class 最长重复子数组718 {

    //暴力破解 转 动态规划
    public int findLength(int[] nums1, int[] nums2) {

        int result = 0;

        //记录以i、j为首字母的字符串的最长重复
        int[][] dp = new int[nums1.length][nums2.length];

        //初始化
        for (int i = 0; i < nums1.length; i++) {
            if( nums1[i] == nums2[nums2.length-1]) {
                dp[i][nums2.length - 1] = 1;
                result = 1;
            }
        }
        for (int j = 0; j < nums2.length; j++) {
            if( nums1[nums1.length-1] == nums2[j]) {
                dp[nums1.length - 1][j] = 1;
                result = 1;
            }
        }

        //从后向前推到
        //踩坑：这里要从 -2 开始（而不是 -1）
        for (int i = nums1.length-2; i >= 0; i--) {
            for (int j = nums2.length-2; j >= 0; j--) {

                //注意，这里dp数组没有在更新是进行max比较，所以它存的是当前解，而不是局部最优解

                //如果相同，加上后边相同的就是总长度
                if(nums1[i] == nums2[j])
                    dp[i][j] = dp[i+1][j+1] + 1;
                //如果不相同，直接置为0
                else
                    dp[i][j] = 0;

                result = Math.max(result, dp[i][j]);
            }
        }

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45