'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