题解 | JAVA DP #最长上升子序列(一)# [P0-T2]

   1 2 5 5 7 8  global-max
2  0 1 0 0 0 0     1
5  0 0 1 1 0 0     1
7  0 0 0 0 2 0     2
8  0 0 0 0 0 3     3
5  0 0 1 1 0 0     3

dp[i][j]: length of common-sequence ending on A[i] and B[i]
dp[i][j] = max {
  d[i-1][j-1] + 1  ~ A[i] = B[j]
  0                 ~ A[i] != B[i]
}

// No space optimization
// Space O(m*n)
// Time  O(m*n)
import java.util.*;

public class Solution {
    public int longestCommonSubarry (int[] A, int[] B) {
      // padded with 0 at beginning
      int dp[][] = new int[A.length+1][B.length+1];
      int max = 0;
      for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= B.length; j++) {
          dp[i][j] = A[i-1] == B[j-1] ? dp[i-1][j-1] + 1 : 0;
          max = Math.max(max, dp[i][j]);
        }
      }
     
      return max;
    }
}

// 2D -> 1D space optimize
// Space O(n)
// Time  O(m*n)
public class Solution {
    public int longestCommonSubarry (int[] A, int[] B) {
      // let A always be the shorter array
      if (A.length > B.length) {
        int[] tmp = A; A = B; B = A;
      }
      
      // pad dp[0] === 0
      int[] dp = new int[B.length+1];
      int maxLen = 0;  // global max
     
      for (int i = 1; i < A.length+1; i++) {  // dp[0][j] === 0
        // reverser j to prevent dirty wrties
        for (int j = B.length; j >= 1; j--) { // dp[i][0] === 0
          if (A[i-1] == B[j-1]) 
            dp[j] = dp[j-1] + 1;
          else 
            dp[j] = 0;
            
          maxLen = Math.max(dp[j], maxLen);
        }
      }
      
      return maxLen;
    }
}