uncrossed-lines

/*
Runtime: 12 ms, faster than 57.50% of C++ online submissions for Uncrossed Lines.
Memory Usage: 8.7 MB, less than 93.94% of C++ online submissions for Uncrossed Lines.
*/
class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int lt[501] = {}, nxt[501] = {}, mx[501] = {};
        for(int i = 0; i < B.size(); i++) {
            lt[i] = (B[i]==A[0]);
            mx[i] = i>0 ? max(mx[i-1], lt[i]) : lt[i];
        }
        for(int i = 1; i < A.size(); i++) {
            for(int j = 0; j < B.size(); j++) {
                int x = j>0 ? mx[j-1] : 0;
                nxt[j] = max(lt[j], x+(A[i]==B[j]));
            }
            for(int j = 0; j < B.size(); j++) {
                lt[j] = nxt[j];
                mx[j] = j>0 ? max(mx[j-1], lt[j]) : lt[j];
            }
            memset(nxt, 0, sizeof(nxt));
        }
        return mx[B.size()-1];
    }
};