9 lines Java DP solution


  • 0
    J

    dp[i][j] refers to the length of maximum subarray that ends with A[i] and B[j].
    i.e. if A[i] == B[j], dp[i][j] = 1 + dp[i-1][j-1], or 0 otherwise

    public int findLength(int[] A, int[] B) {
         int res = 0;
         int[][] dp = new int[A.length][B.length]; // store the max sub array length for subarray ending with i & j
         for (int i = 0; i < A.length; i++) {
             for (int j = 0; j < B.length; j++) {
                 dp[i][j] = A[i] == B[j] ? 1 + (i > 0 && j > 0 ? dp[i-1][j-1] : 0) : 0; 
                 res = Integer.max(dp[i][j], res);
             }
         }
         return res;
    }
    

Log in to reply
 

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