## 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);
}
}