return the array instead of the length? Very simple dp solution with the both max and the array


  • 1
    E

    What if you asked to return the array instead of the length! No worries
    let's first fill our 2D dp array. The question here is how?
    let's use the example given in the problem
    eg
    A = {1,2,3,2,1}
    B = {3,2,1,4,7}
    0_1511474399873_Screen Shot 2017-11-23 at 4.59.28 PM.png

    that is the initial dp array of size [A.length+1][B.length+1]

    so let's fill the third and fourth row to get a pattern of how our dp formula should look like.
    0_1511476366531_Screen Shot 2017-11-23 at 5.32.33 PM.png
    If the number is the same we get the element at position i-1 and j-1 and add 1 to it and store it at dp[i][j] .
    After filling the whole array then the length of the longest gives you the answer you can keep tract of it with a max variable.
    The complete table is showed below
    0_1511476664902_Screen Shot 2017-11-23 at 5.37.14 PM.png

    public int findLength(int[] A, int[] B) {
         int max = 0;
         int[][] dp = new int[A.length+1][B.length+1];
            for(int i=1; i<dp.length; i++){
                for(int j=1; j<dp[i].length;j++){
                    if(B[i-1] == A[j-1]){  		
                    	if((dp[i][j] = dp[i-1][j-1] + 1) > max){
                    		 max = dp[i][j] = dp[i-1][j-1] +1;
                    	}
                    }
                  }
            }   
        return max;
    }
    

    That returns the longest length from the array.

    What happens if you are asked to return the array instead of length.
    It's actually so easy go back to the dp array and just back trace it. We need to modify the above above to keep tract of the i-th and j-th index of the max for easy backtracking.
    After observing the table just back trace starting from either of index whether i-th of j-th you will get the same result

     public int findLength(int[] A, int[] B) {
    	 int maxIindex = 0;
         int maxJindex = 0;
         int max = 0;
            int[][] dp = new int[A.length+1][B.length+1];
            for(int i=1; i<dp.length; i++){
                for(int j=1; j<dp[i].length;j++){
                    if(B[i-1] == A[j-1]){  		
                    	if((dp[i][j] = dp[i-1][j-1] + 1) > max){
                    		max = dp[i][j] = dp[i-1][j-1] + 1;
                    		maxIindex = i;
                   	        maxJindex = j ;
                    	}
                    }
                  }
            }
            
            int[] result = new int[max];
            int k = result.length-1;
            while(k>=0){	
            		result[k] = B[maxIindex-1];
            		maxIindex--;
            		k--;
            }  
        System.out.println(Arrays.toString(result)); 
        return max;
    }

Log in to reply
 

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