'How to print the optimal route to get the max path sum in a matrix
Here is my code for finding the maximum weight in a n x m matrix.
public static int[][] maxSum(int[][] matrix, int m, int n) {
int[][] totalWeight = new int[m+1][n+1];
int rightSum = 0, downSum = 0, diagonalSum = 0;
totalWeight[0][0] = matrix[0][0];
//fill the first row of totalWeight array from matrix array row
for (int i = 1; i < matrix.length; i++) {
totalWeight[i][0] =totalWeight[i-1][0] + matrix[i][0];
}
//fill the first column of totalWeight array from matrix array column
for (int j = 1; j < matrix.length; j++) {
totalWeight[0][j]=totalWeight[0][j-1] + matrix[0][j];
}
//fill the remaining indices with the max value
for (int i = 1; i < totalWeight.length; i++)
for (int j = 1; j < totalWeight.length; j++) {
rightSum=totalWeight[i-1][j]+matrix[i][j];
downSum=totalWeight[i][j-1]+matrix[i][j];
diagonalSum=totalWeight[i-1][j-1]+matrix[i][j];
totalWeight[i][j] = Math.max(rightSum,Math.max(downSum,diagonalSum));
}
return totalWeight;
}
You start at top left index and can move down, right or diagonally to get to the bottom right index.
I need help finding a way to print the path from index (0,0) to the index (n,m) that will give the maximum sum.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|