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

示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释: 
长度最长的公共子数组是 [3, 2, 1]。
说明:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

 

 

思路：

    动态规划问题 dp[i][j]表示数组A到i时 数组B到j时 最大公共子数组长度
    若A[i]==B[j]最后一个字符相等 则dp[i][j]=dp[i-1][j-1]+1
    A[i]=B[j]不等时 dp[i][j]=Max(dp[i][j-1],dp[i-1][j])  由于在一直保存最大值res  所以不相等时  不用理会

public int findLength(int[] A, int[] B) {
		int res = 0;
		int[][] dp = new int[A.length][B.length];
		for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < B.length; j++) {
				if (A[i] == B[j]) {  //相等情况
					if (i != 0 && j != 0) {
						dp[i][j] = dp[i - 1][j - 1] + 1;
						if (dp[i][j] > res) {
							res = dp[i][j];
						}
					} else {    //i和j都为0
						dp[i][j] = 1;
					}
				}
			}
		}
		return res;
	}