Блог

Вот мой код для нахождения максимального веса в матрице n x m.

     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;

    }
 

Вы начинаете с верхнего левого индекса и можете двигаться вниз, вправо или по диагонали, чтобы добраться до нижнего правого индекса.

Мне нужна помощь в поиске способа вывести путь от индекса (0,0) до индекса (n,m), который даст максимальную сумму.