class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int result = 0;

        // dp[i][j]: max length when (i,j)
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    // (i,j) depends on (i-1, j-1) is valid
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                result = max(result, dp[i][j]);
            }
        }

        return result;
    }
};

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int result = 0;

        vector<int> dp(n+1);
        
        for(int i = 1; i <= m; i++) {
            for(int j = n; j >= 1; j--) {
                if(nums1[i-1] == nums2[j-1]) {
                    dp[j] = dp[j-1] + 1;
                } else {
                    dp[j] = 0;
                }
                result = max(result, dp[j]);
            }
        }

        return result;
    }
};