Max Summe in einem 2d Array Java

Question

Ich habe ein 2d Array (eine Matrix) und ich muss die maximale Summe finden, die gesammelt werden kann, indem ich an irgendeiner Position anfange und nach rechts oder unten links gehe, bis ich ein Ende erreiche. Ich muss eine iterative Lösung geben.

Das ist mein Code

static int maxValue(double[][] field, int posR, int posC) { 
    int r = field.length; 
    int c = field[0].length; 
    int sum = 0; 
    double[][] temp = new double[r][c]; 
    for (int i = posR; i < r; i++) { 
     for (int j = posC; j < c; j++) { 
      if (i == posR && j == posC) { 
       temp[i][j] = field[posR][posC]; 
       posR++; posC++; 
      } else if (i == field.length-1) { 
       temp[i][j] = field[i][j]; 
       break; 
      } else if (j == field.length-1) { 
       temp[i][j] = field[i][j]; 
       break; 
      } else { 
       temp[i][j] = Math.max(field[i+1][j-1], field[i+1][j+1]); 
      } 
     } 
    } 
    for (int i = 0; i < r; i++) { 
     for (int j = 0; j < c; j++) { 
      sum += temp[i][j]; 
     } 

    } 
    return sum; 
} 

}

Answer 1

Hier ist eine Idee für eine iterative Lösung: Sie können eine Reihe nach unten schieben und unten finden Sie die max. Klingt verrückt? Lassen Sie mich mit dem Code erklären:

public static double maxZicZacSum(double[][] matrix) { 
    double[] row = matrix[0]; // assign first row 
    int n = row.length; 
    for (int i = 1; i < matrix.length; i++) { // for each row, except the first 
    double[] nextRow = new double[n]; 
    // special cases (left and right edge) 
    nextRow[0] = row[1] <= 0 ? matrix[i][0] : row[1] + matrix[i][0]; 
    nextRow[n - 1] = row[n - 2] <= 0 ? matrix[i][n - 1] : row[n - 2] + matrix[i][n - 1]; 
    for (int j = 1; j < n - 1; j++) { // for each column except the edges 
     double d = Math.max(row[j - 1], row[j + 1]); // which cell above is better? 
     // if d is > 0, then the sum is also better, otherwise use (i,j) as new start 
     nextRow[j] = d <= 0 ? matrix[i][j] : d + matrix[i][j]; 
    } 
    row = nextRow; // finally assign nextRow to row for the next iteration 
    } 
    // the highest value in row is now the max sum 
    double max = row[0]; 
    for (int i = 1; i < n; i++) 
    if (row[i] > max) 
     max = row[i]; 
    return max; 
} 

Answer 2

Allgemein gesprochen ist, ist dies ein dynamisches Programmierproblem.

Die Logik ist (mit der Zeile 0 die oben links)

F(row, col) = valueAt(row, col) + max(F(row + 1, col - 1), F(row + 1, col + 1) 

Jetzt werden Sie feststellen, das eine rekursive Definition ist, so dass keine for-Schleifen sind wirklich benötigt wird.

Also, in leichten Pseudo-Code

int maxValue(double[][] arr, int row, int col) { 
    if (outOfBounds) return 0; 

    int value = arr[row][col]; 
    int leftDiag = maxValue(arr, row +1,col - 1); 
    int rightDiag = maxValue(arr, row + 1, col + 1); 
    return value + Math.max(leftDiag, rightDiag); 
} 

an einer beliebigen Position starten, sollten Sie in der Lage sein, die Methode aufzurufen und es wird rekursiv Werte summieren und den maximalen Pfad zurückzukehren.