代碼題（60）— 最長重複子數組

1、718. 最長重複子數組

給兩個整數數組 

A

 和 

B

 ，傳回兩個數組中公共的、長度最長的子數組的長度。

示例 1:

輸入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
輸出: 3
解釋: 
長度最長的公共子數組是 [3, 2, 1]。      

　　這道題給了我們兩個數組A和B，讓我們傳回連個數組的最長重複子數組。那麼如果我們将數組換成字元串，實際這道題就是求Longest Common Substring的問題了，而貌似LeetCode上并沒有這種明顯的要求最長相同子串的題，注意需要跟最長子序列Longest Common Subsequence區分開，關于最長子序列會在follow up中讨論。好，先來看這道題，對于這種求極值的問題，DP是不二之選，我們使用一個二維的DP數組，其中dp[i][j]表示數組A的前i個數字和數組B的前j個數字的最長子數組的長度，如果dp[i][j]不為0，則A中第i個數組和B中第j個數字必須相等，比對于這兩個數組[1,2,2]和[3,1,2]，我們的dp數組為：

3 1 2
1 0 1 0
2 0 0 2
2 0 0 1      

我們注意觀察，dp值不為0的地方，都是當A[i] == B[j]的地方，而且還要加上左上方的dp值，即dp[i-1][j-1]，是以目前的dp[i][j]就等于dp[i-1][j-1] + 1，而一旦A[i] != B[j]時，直接指派為0，不用多想，因為子數組是要連續的，一旦不比對了，就不能再增加長度了。我們每次算出一個dp值，都要用來更新結果res，這樣就能得到最長相同子數組的長度了，參見代碼如下：

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        if(A.empty() || B.empty())
            return 0;
        int res = 0;
        vector<vector<int>> dp(A.size()+1,vector<int>(B.size()+1,0));
        for(int i=1;i<=A.size();++i)
        {
            for(int j=1;j<=B.size();++j)
            {
                if(A[i-1]==B[j-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = 0;
                res = max(res,dp[i][j]);
            }
        }
        return res;
    }
};      

轉載于:https://www.cnblogs.com/eilearn/p/9555056.html