package com.interview.dynamic;

/**
 http://www.geeksforgeeks.org/longest-common-substring/
 */
public class LongestCommonSubsequence {

    public int lcs(char str1[],char str2[],int len1, int len2){
        
        if(len1 == str1.length || len2 == str2.length){
            return 0;
        }
        if(str1[len1] == str2[len2]){
            return 1 + lcs(str1,str2,len1+1,len2+1);
        }
        else{
            return Math.max(lcs(str1,str2,len1+1,len2),lcs(str1,str2,len1,len2+1));
        }
    }

    public int lcsDynamic(char str1[],char str2[]){
    
        int temp[][] = new int[str1.length + 1][str2.length + 1];
        int max = 0;
        for(int i=1; i < temp.length; i++){
            for(int j=1; j < temp[i].length; j++){
                temp[i][j] = Math.max(temp[i][j-1],temp[i-1][j]);
                if(str1[i-1] == str2[j-1]){
                    temp[i][j] = temp[i-1][j-1] + 1;
                    if(temp[i][j] > max){
                        max = temp[i][j];
                    }
                }
            }
        }
        return max;
    
    }
    
    public static void main(String args[]){
        LongestCommonSubsequence lcs = new LongestCommonSubsequence();
        String str1 = "ABCDGHLQR";
        String str2 = "AEDPHR";
        
        int result = lcs.lcsDynamic(str1.toCharArray(), str2.toCharArray());
        System.out.print(result);
    }
    
    
    
}

@@ -766,30 +766,57 @@
     
-temp%5Bi%5D%5Bj%5D = Math.max(
+if(str1%5Bi-1%5D == str2%5Bj-1%5D) %7B%0A                    
 temp
@@ -824,25 +824,34 @@
 i%5D%5Bj
--1%5D,
+%5D = 
 temp%5Bi
--
+ - 
 1%5D%5Bj
-%5D)
+ - 1%5D + 1
 ;%0A  
@@ -868,34 +868,47 @@
     
-if(str1%5Bi-1%5D == str2%5Bj-1%5D)
+%7D%0A                else%0A                
 %7B%0A  
@@ -942,32 +942,63 @@
 %5D = 
+Math.max(
 temp%5Bi
--1
 %5D%5Bj-1%5D
- + 1;%0A    
+,temp%5Bi-1%5D%5Bj%5D);%0A                %7D%0A
     
@@ -1051,20 +1051,16 @@
         
-    
 max = te
@@ -1073,30 +1073,8 @@
 j%5D;%0A
-                    %7D%0A
     

Update LongestCommonSubsequence