CODEWITHSUNDEEP
javaarraysmultidimensional-array
MetaTron
MetaTron

Reputation: 1091

Max sum in a 2d array Java

I have a 2d array (a matrix) and I need to find the max sum that can be collected by starting at any position and going down right or down left until I reach an end. I must give an iterative solution.

enter image description here

This is my 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;
}

}

Upvotes: 2

Views: 1561

Answers (2)

maraca
maraca

Reputation: 8743

Here is an idea for an iterative solution: You can slide down a row and at the bottom you will find the max. Sounds crazy? Let me explain with code:

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;
}

Upvotes: 1

OneCricketeer
OneCricketeer

Reputation: 191701

Generally speaking, this is a dynamic programming problem.

The logic is (with row 0 being the top left) 

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

Now, you'll notice this is a recursive definition, so no for loops are really needed.

So, in slight pseudocode 

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);
}

Starting at any position, you should be able to call the method and it'll recursively sum values and return the max path.

Upvotes: 0

Related Questions