Tuesday 6 December 2016

Maximum weight path ending of last row in a matrix

Find the path having the maximum weight in integer matrix [N X M].

Conditions for moves:
Path should begin from top left element and can end at any element of last row. We can move to down (i+1, j) or diagonal forward (i+1, j+1).

public class MaxWeightPathMatrix {
    
     /**
      * Moves # down or forward diagonal.
      * @param matrix
      * @return Returns the maximum weight.
      */
     private static int getMaxWeightPath(int[][] matrix) {

           int row = matrix.length;
           int col = matrix[0].length;

           int[][] dp = new int[row][col];

           /** Initialize first row of total weight */
           for(int i=0;i<col;i++) {
                dp[0][i] = matrix[0][i];
           }

           /** Initialize first column of total weight */
           for (int i=1; i<row; i++) {
                dp[i][0] = matrix[i][0] + dp[i-1][0];
           }

           for(int i=1; i<row; i++) {
                for(int j=1; j<col; j++) {
                     dp[i][j] = matrix[i][j] + Math.max(dp[i-1][j],
                                dp[i-1][j-1]);
                }
           }

           /** Max weight path sum to rech the last row */
           int result = 0;
           for (int i=0; i<col; i++) {
                result = Math.max(dp[row-1][i], result);
           }
           return result;
     }
    
     /** Driver method. */
     public static void main(String[] args) {
          
           int[][] matrix = {{ 8, 4 ,6 ,8 ,2 },
                     { 4 , 18 ,2 ,20 ,10 },
                     {20, 2 ,6 , 0 ,40 },
                     {32 ,184, 82, 88 ,2},
                     {16, 302, 12, 8, 18}};

           int maxWeight = getMaxWeightPath(matrix);

           System.out.println("Maximum weight path ending at any"
                     + " element of last row in a matrix # "+ maxWeight);
     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...