Максимальный путь с 2D-массивом в java, произвольная ячейка для начала - PullRequest
Новая
       73

Максимальный путь с 2D-массивом в java, произвольная ячейка для начала

0 голосов
/ 04 августа 2020

Я хотел напечатать максимальное значение, которое вы можете накопить при перемещении по 2D-массиву, пока go не выйдете за границы 2D. Обратите внимание: пользователь либо перемещается вправо, либо к кнопке на 2D-массиве. Например Пример ввода и вывода

, поэтому я пишу код, подобный следующему 

public static int find(int[][] A) {
    int[][] solution = new int[A.length][A.length];

    solution[0][0] = A[0][0];
    // fill the first row
    for (int i = 1; i < A.length; i++) {
        solution[0][i] = A[0][i] + solution[0][i - 1];
    }

    // fill the first column
    for (int i = 1; i < A.length; i++) {
        
        solution[i][0] = A[i][0] + solution[i - 1][0];
    }

    // path will be either from top or left, choose which ever is maximum
    int temp=0;
    for (int i = 1; i < A.length; i++) {
        for (int j = 1; j < A.length; j++) {
           // if ((A[i][j]+ Math.max(solution[i - 1][j], solution[i][j - 1])) >A[i][j] )
            solution[i][j] = A[i][j]
                    + Math.max(solution[i - 1][j], solution[i][j - 1]);
                //  else solution[i][j] = A[i][j];
                    
        }
    }
    int temp1 = 0;
    int temp2 =0;
    for(int i=0; i< A.length; i++){
       // System.out.println(" temp1= "+temp1);
        if(solution[i][A.length-1] > temp1) temp1= solution[i][A.length-1];
        //System.out.println(" temp1= "+temp1);
        if(solution[A.length-1][i] > temp2) temp2= solution[A.length-1][i];
       // System.out.println(" temp2= "+temp2);
    }
    for(int i=0; i< A.length; i++){
        for (int j=0; j< A.length;j++){
            System.out.print(solution[i][j]+"\t");
        }
         System.out.println(" ");
    }
    return Math.max(temp1,temp2);
    
}

, но он дает мне 592 в качестве вывода и я не знаю, где проблема в моем коде.

Ответы [ 2 ]

1 голос
/ 05 августа 2020

Проблема говорит, что максимальное значение, которое вы можете накопить при перемещении по 2D-массиву , поэтому путь максимальной суммы может начинаться откуда угодно и заканчиваться где угодно. Вы должны продолжать максимизировать результат в каждом месте (i,j). Максимальное значение для каждого местоположения может быть одним из трех ниже:

  • Значение в самом местоположении: A[i][j]

  • Значение + максимум, когда вы идете сверху: d[i-1][j] + A[i][j]

  • Значение + максимум, когда вы идете слева: d[i][j-1] + A[i][j]

Вы должны взять максимум из этих трех.

Код: 

public static int find(int[][] A) {
     int R = A.length;
     int C = A[0].length;
     int[][] d = new int[R+1][C+1];
     int res = Integer.MIN_VALUE;
     for ( int i = 1; i <= R; i++ ) {
       for ( int j = 1; j <= C; j++ ) {
          d[i][j] = Math.max( A[i-1][j-1], Math.max(d[i][j-1] + A[i-1][j-1], d[i-1][j] + A[i-1][j-1]));
          res = Math.max( res, d[i][j]);
       }
     }
     return res;
   }

Вывод: 603

Вы можете играть с этим кодом здесь

0 голосов
/ 04 августа 2020

Изменить: Похоже, мой код такой же, как и ваш ... В общем, у меня 547. Максимальное значение будет solution[A.length-1][A.length-1].

.

Оригинальный ответ: Вот что я получил, используя javascript (547) - я уверен, что вы можете «перевести» его на любой язык по вашему выбору: 

var inputArray=[
  [-45,  87, -43, -12,   3, -39, -61, -19],
  [ 97, -64,  79, -75,  19,  97,  80,  12],
  [-24, -62,  46,  97, -75, -45,  92,  69],
  [ 87, -31,  74,  33, -49,   1,  27,  95],
  [ 13, -82, -19,  14, -76,  95,  64, -33],
  [-25,  45, -61,  90, -90,  43,  32,  96],
  [-27,  38,  77, -42,  36,  71,  32,  30],
  [ 27, -52, -66, -78, -42,  66,  69, -11]
];
console.log(JSON.stringify(inputArray));

var maxArray=[];
for(var i=0; i<inputArray.length; i++) {
  maxArray[i]=[];
  for(var j=0; j<inputArray.length; j++) {
    maxArray[i][j]=0;
  }
}
console.log(JSON.stringify(maxArray));

maxArray[0][0]=inputArray[0][0];
for(var i=1; i<inputArray.length; i++) {
  maxArray[0][i]=maxArray[0][i-1]+inputArray[0][i];
  maxArray[i][0]=maxArray[i-1][0]+inputArray[i][0];
}
console.log(JSON.stringify(maxArray));

for(var i=1; i<inputArray.length; i++) {
  for(var j=1; j<inputArray.length; j++) {
    maxArray[i][j]=Math.max(maxArray[i-1][j], maxArray[i][j-1]) + inputArray[i][j];
  }
}
console.log(JSON.stringify(maxArray));

var max=maxArray[inputArray.length-1][inputArray.length-1];
console.log("Max="+max);

Я использовал console.table вместо console.log(JSON.stringify, но сниппет его не поддерживает. Я записал результаты каждого шага. Сначала я создал массив такой же размерности, заполненный нулями. Затем я скопировал значение первого столбца / строки. Затем я заполнил оставшуюся часть первой строки и первого столбца, добавив inputArray и значения влево / вверх. Затем я заполнил оставшуюся часть матрицы, добавив inputArray и max left / up. Последний столбец содержит максимальные значения, если вы go справа, а последняя строка - снизу. Самый дальний угол будет абсолютным максимумом - и я это зарегистрировал.

...