【Leetcode】718. 最长重复子数组

最长重复子数组有一下性质

A: [1,2,3,2,1]

B: [3,2,1,4,7]
设横是A竖是B，有规律：若横元和竖元相等，则为1，不等为0
  1 2 3 2 1
3 0 0 1 0 1
2 0 1 0 1 0
1 1 0 0 0 1
4 0 0 0 0 0
7 0 0 0 0 0

可见最长子数组坐标是(0,2)(1,4)(2,5)

设计dp二维数组，若横元和竖元相等，dp[i][j]=dp[i-1][j-1]有
  1 2 3 2 1
3 0 0 1 0 1
2 0 1 0 2 0
1 1 0 0 0 3
4 0 0 0 0 0
7 0 0 0 0 0
则其中最大值3就是答案

class Solution {

    int dp[1001][1001];

public:

    int findLength(vector<int>& A, vector<int>& B) {

        memset(dp, 0, sizeof(dp));

        int M = A.size(), N = B.size(), ans = 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;

                    ans = max(ans, dp[i][j]);

                }

            }

        }

        return ans;

    }

};

巴特西

【Leetcode】718. 最长重复子数组

最新文章

热门文章