leetcode-go/leetcode/medium/718.cc

#include <vector>
#include <cstring>
#include <algorithm>

using std::vector;
using std::max;

#define L 1000

int dp[L + 1][L + 1];

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        // dp[i][j] means the max length of subarray end at A[i + 1] and B[j + 1]
        memset(dp, 0, sizeof(dp));
        int len = 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;
                    len = max(len, dp[i][j]);
                }
            }
        }
        return len;
    }
};

#include <cstdio>

int main() {
    Solution *sol = new Solution();

    vector<int> a = {1, 3, 1, 2, 1};
    vector<int> b = {3, 2, 1, 4, 7};
    int ans = sol->findLength(a, b);
    printf("%d\n", ans);

    a = {1, 2, 3, 2, 1};
    b = {3, 2, 1, 4, 7};
    ans = sol->findLength(a, b);
    printf("%d\n", ans);

    return 0;
}