题目分析

这个题目小伙伴们看起来是否有些眼熟，有没有想到动态规划的经典算法最长公共子序列？本题能否也按着这个想法来思考呢？

DP

子序列和子数组的差异在于，子序列的元素是不连续的，而本题的元素是连续的。在最长公共子序列中，用dp[i][j]表示num1前i个数字和num2前j个数字的最长公共子序列。
$$dp[i][j] = \begin{case} dp[i - 1][j - 1] + 1 & num1[i - 1] = num2[j - 1] \ max(dp[i - 1][j], dp[i][j - 1]) & num1[i - 1] \ne num2[j - 1] \end{cases}$$

本题类似的dp[i][j]表示以num1[i - 1]和num2[j - 1]结尾的最长公共子数组。
$$dp[i][j] = \begin{case} dp[i - 1][j - 1] + 1 & num1[i - 1] = num2[j - 1] \ 0 & num1[i - 1] \ne num2[j - 1] \end{cases}$$

dp[i]仅仅和dp[i - 1]有关，为了节省空间可以使用一维DP进行计算，算法的**时间复杂度为$O(nm)$，空间复杂度为$O(min(n, m))$**。

下面是Java语言的题解

public int findLength(int[] nums1, int[] nums2) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    int[] dp = new int[len2 + 1];
    int res = 0;
    for (int i = 1; i <= len1; i++) {
        for (int j = len2; j >= 1; j--) {
            dp[j] = nums1[i - 1] == nums2[j - 1] ? dp[j - 1] + 1 : 0;
            res = Math.max(res, dp[j]);
        }
    }
    return res;
}

刷题总结

话不多说，最长公共子序列，最长公共子数组，最长递增子序列都是经典题目，请小伙伴们无比烂熟于心。