Simple O(nm) DP solution


  • 2
    E

    dp[i][j] is the max repeated length if the subarray in a ends at index i-1 and subarray in b ends at index j-1

    class Solution {
    public:
        int findLength(vector<int>& a, vector<int>& b) {
            int na = a.size(), nb= b.size();
            int dp[na+1][nb+1] = {};
            int mx = 0;
            for (int i = 1; i <= na; ++i) for (int j = 1; j <=nb; ++j) {
                if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                mx = max(mx,dp[i][j]);
            }
            
            return mx;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.