Max sum in a 2d array Java

Question

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

}

@ Sanjeev, it works, but the problem is that it doesn't give the right answer. — MetaTron
– MetaTron, Commented Jul 31, 2016 at 14:41
What is the idea behind the code? You seem to be taking the sum from an area instead of a line. — maraca
– maraca, Commented Jul 31, 2016 at 14:53
@ maraca, maybe this is the problem. Can you suggest how to fix the code in order to take the sum from a line? Thank you so much! — MetaTron
– MetaTron, Commented Jul 31, 2016 at 14:59
I am not sure what kind of sum you are trying to get from a given matrices, can you please take an example matrices and explain the problem — Sanjeev
– Sanjeev, Commented Jul 31, 2016 at 15:07

maraca · Accepted Answer · 2016-07-31 19:16:04Z

1

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

answered Jul 31, 2016 at 19:16

maraca

9,5873 gold badges27 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

MetaTron Over a year ago

THANK YOU! It works perfectly. Do you know how to make it work for any start position, not only from the top?

maraca Over a year ago

This is for any position in the matrix. You see that a new starting point may be chosen along the way if it is better.... I was wrong, don't need to make a copy of the first row, because the values are assigned to nextRow.

maraca Over a year ago

Thanks for accepting, the mistake isn't one, because you have to go to the end from any starting position right? You can't stop somewhere. Then the solution is correct.

MetaTron Over a year ago

It's OK. It doesn't have to work with negative numbers. But I think there is another problem. I have a recursive solution for this problem and both solutions give different answer for the same position :(

maraca Over a year ago

Hard to say, you can post a new question with the recursive code ;-) Now after writing an iterative solution my recursive one would just be "fake" I think. Any loop can be turned into recursion...

OneCricketeer · Accepted Answer · 2016-07-31 15:30:09Z

0

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.

answered Jul 31, 2016 at 15:30

OneCricketeer

193k20 gold badges146 silver badges276 bronze badges

4 Comments

MetaTron Over a year ago

I am not allowed to use recursion for this problem. They ask me to give an iterative solution :( Thank you for your answer!

OneCricketeer Over a year ago

It iterates recursively ;) I get what you're saying, though. I never understood why assignments make themselves harder then they need to be

MetaTron Over a year ago

Another part of my assignment is do solve the problem with recursion. But this one is killing me :D

OneCricketeer Over a year ago

I was thinking about it a bit, and you'd be best of writing some iterative methods like maxLeft() maxRight() that end iteration when they hit out of bounds. The tricky part is "zigzag"-ing down the array, though

Collectives™ on Stack Overflow

Max sum in a 2d array Java

2 Answers 2

5 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related