718. Maximum Length of Repeated Subarray

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000

2. 0 <= A[i], B[i] < 100

利用2-D DP array紀錄中間過程，dp[i][j]代表以A[i - 1]和B[j - 1]結尾的兩個子數列最長的重複長度。 DP關係式為 dp[i][j] = dp[i - 1][j - 1] + 1 if A[i - 1] == B[j - 1]

// Dynamic programming
int findLength(vector<int>& A, vector<int>& B) { // time: O(m * n); space: O(m * n)
    int m = A.size(), n = B.size(), res = 0;
    vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                res = max(res, dp[i][j]);
            }
        }
    }
    return res;
}

發現其實只用到前一個row的資訊去更新，所以可以不需要用到2-D array，注意如果要用1-D array去紀錄中間過程，column的loop方向要從大到小。

// Space Optimized Dynamic programming
int findLength(vector<int>& A, vector<int>& B) { // time: O(m * n); space: O(n)
    int m = A.size(), n = B.size(), res = 0;
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= m; ++i) {
        for (int j = n; j >= 1; --j) {
            if (A[i - 1] == B[j - 1]) {
                dp[j] = dp[j - 1] + 1;
                res = max(res, dp[j]);
            } else {
                dp[j] = 0;
            }
        }
    }
    return res;
}