想要精通算法和SQL的成长之路 - 最长序列问题

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 最长递增子序列

原题链接

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

• 输入：nums = [10,9,2,5,3,7,101,18]
• 输出：4
• 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

思路：

1. 假设dp[i]代表：以num[i]为结尾的最大递增子序列的长度。
2. 那么dp[i+1]和dp[i]的关系是什么？注意：本题目当中的递增序列不要求是连续的。因此在 [0,i] 这个区间内，只要存在一个元素num[j]比 num[i+1] 小，那么就存在 dp[i+1] = dp[j] +1。

假设[0,i]这个区间内，有两个元素比num[i+1]小，假设下标分别为1和3。那么就有：

dp[i+1] = dp[1] +1；
dp[i+1] = dp[3] +1；
1
2

既然我们要求得最长的递增序列。自然而然需要取Max：

dp[i+1]  = max(dp[1] +1, dp[3] +1, dp[i+1]);
1

那么自然而然地我们就需要对[0,i]这个区间的元素都做一次比较。那么就得出代码：

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);
        }
    }
}
1
2
3
4
5
6
7

这次遍历我们求得的是以每个元素为截止位置的时候的最长递增子序列，因此我们还需要另外一个变量res存储其中的最大值。

初始化操作：每个元素为截止位置的时候的最长递增子序列最小都是1。

int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
1
2

最终代码就是：

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int[] dp = new int[nums.length];
    int res = 0;
    // 初始化数组，以每个位置为终点的最小子序列为1
    Arrays.fill(dp, 1);
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
        	// 如果当前位置num[i]比之前的某一个元素num[j]大，那么num[j]只能说可能作为最终最长递增子序列的一部分。
        	// 因此这里要进行比较，取最大值。
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二. 最长连续递增子序列

原题链接

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

• 输入：nums = [1,3,5,4,7]
• 输出：3
• 解释：最长连续递增序列是 [1,3,5], 长度为3。
  尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

在第一题的基础上，也就是要求连续而已。

思路：

1. 我们从第一个元素M开始遍历，一旦下一个元素比当前元素大。那么长度加1。
2. 如果发现下一个元素Q反而小了。更新最长的连续递增子序列长度。重新从当前位置Q开始计数。
3. 为什么是以Q为起点计数而不是M+1？因为到Q为止，我们已经保证了[M,Q-1]这个区间范围内的元素都是递增的。它的最长连续递增子序列的长度就是其本身。总不可能[M+1,Q-1]这个区间的长度比它还要大吧？

这里的思想可以说是一种贪心。写成代码就是：

public int findLengthOfLCIS(int[] nums) {
    int res = 0;
    // 最小的连续递增子序列为1
    int count = 1;
    for (int i = 0; i < nums.length - 1; i++) {
        // 开始计递增长度
        if (nums[i + 1] > nums[i]) {
            count++;
        } else {
            // 一旦发现递增中断了，更新长度以及重新计长
            res = Math.max(count, res);
            count = 1;
        }
    }
    // 这里是为了避免上面的for循环全部都是递增的情况
    return Math.max(count, res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三. 最长重复子数组

原题链接

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

• 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
• 输出：3
• 解释：长度最长的公共子数组是 [3,2,1] 。

这题是在第二题的基础上，给了你俩数组来取重复的连续交集部分。思路：

1. 这里面和前面两题有一个不同的点就是，由于取的是两个数组的一个交集。因此可能不存在交集，因此最长重复子数组可能为0。
2. 我们定义dp[i][j]：在num1中以i-1为结尾。在num2中以j-1为结尾的最长重复子数组的长度。
3. 那么有且仅当num1[i] == nums2[j] 的时候有递推公式：dp[i+1][j+1] = dp[i][j] + 1。否则其余情况下都是不存在重合部分的，也就是dp[i][j]默认值是0。这部分我们甚至都不用管。

public int findLength(int[] nums1, int[] nums2) {
    int res = 0;
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];

    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 - 1][j - 1] = 0，那么当前的最长重复子序列就是1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // 更新最大值
            res = Math.max(res, dp[i][j]);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

四. 最长公共子序列

原题链接

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

示例 1：

• 输入：text1 = “abcde”, text2 = “ace”
• 输出：3
• 解释：最长公共子序列是 “ace” ，它的长度为 3 。

这题目又是上面几题的一个升华：

• 可以删除字符，即不要求连续。（第一题）
• 在两个字符串（集合）中寻找公共部分。（第三题）

那么我们结合上面的思路：

1. 我们定义dp[i][j]：在text1中以[1,i]为区间。在text2中以[1,j]为区间的最长公共子序列长度。
2. 那么如果test1[i-1]和 test2[j-1]相等。那么递推公式：dp[i][j] = dp[i - 1][j - 1] + 1;
3. 那么如果test1[i-1]和 test2[j-1]不相等。 那么dp[i][j] 的值必定是继承自之前区间的大小。那么这时候又可以分成两种情况。

dp[i][j-1]：在text1中以[1,i]为区间。在text2中以[1,j-1]为区间的最长公共子序列长度。
dp[i-1][j]: 在text1中以[1,i-1]为区间。在text2中以[1,j]为区间的最长公共子序列长度。

4. 两者取最大值。

public int longestCommonSubsequence(String text1, String text2) {
    int[][] dp = new int[text1.length() + 1][text2.length() + 1];
    int res = 0;
    for (int i = 1; i <= text1.length(); i++) {
        for (int j = 1; j <= text2.length(); j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
            // 更新最大值
            res = Math.max(res, dp[i][j]);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第三题和第四题有啥区别？

• 第三题要求是连续的，所以动态数组定义的时候，可以定义以xxx为结尾的最长序列。
• 第四题不要求连续，但是元素的相对顺序要满足，即可删除。因此需要定义以 [1,xxx]为区间的最长序列。

因此第四题中和第三题相比，多了一个代码：

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
1