educative.io

Why do we need to keep the record of maxLengh?

Courses
,
#1

For the bottom-up dynamic programming approach:

public int findLCSLength(String s1, String s2) {
    int[][] dp = new int[s1.length()+1][s2.length()+1];
    int maxLength = 0;
    for(int i=1; i <= s1.length(); i++) {
      for(int j=1; j <= s2.length(); j++) {
        if(s1.charAt(i-1) == s2.charAt(j-1))
          dp[i][j] = 1 + dp[i-1][j-1];
        else
          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        
        maxLength = Math.max(maxLength, dp[i][j]);  // why do we need this?
      }
    }
    return maxLength;
  }

As we know it for sure that the bottom-right number (i.e., dp[s1.length()][s2.length()] would be the maximum length. why is it necessary to record the maxLength?

4 Likes
#2

Have same concern.