算法DP

(DP) $O(nm)$

转移方程：

Java 代码

class Solution {
    public int findLength(int[] A, int[] B) {
        // dp[i][j]: A[0->i] && B[0, j]最长的公共子数组的长度
        // dp[i][j]: A[i] != A[j]
        // dp[i][j] = dp[i - 1][j - 1] + 1  A[i] = B[j]
        int n = A.length;
        int m = B.length;
        int[] dp = new int[m + 1];
        int max = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= 1; --j) {
                if (A[i-1] == B[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                }
                else dp[j] = 0;
                max = Math.max(max, dp[j]);
            }
        }
        return max;
    }
}