CODEWITHSUNDEEP
algorithmdynamicdynamic-programming
risk9283
risk9283

Reputation: 63

Max path with 2D array in java , arbitrary cell to start

I wanted to print the maximum value you can accumulate while moving on the 2D array until you go off the 2D edges.
Note the user either move to the right or to the button on the 2D array.
For example Sample Input and output

so I write the code like the following

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

but it gives me 592 as an output and didn't know where is the problem in my code.

Upvotes: 0

Views: 143

Answers (2)

SomeDude
SomeDude

Reputation: 14238

The problem says that maximum value you can accumulate while moving on the 2D array, so the path of maximum sum can start from anywhere and end anywhere. You should keep maximizing the result at each location (i,j). The maximum at each location can be one of the three below:

  • The value at the location itself : A[i][j]

  • The value + the maximum so far when you come from top : d[i-1][j] + A[i][j]

  • The value + the maximum so far when you come from left : d[i][j-1] + A[i][j]

You have to take the maximum of those three.

Code:

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

Output : 603

You can play with this code here

Upvotes: 1

iAmOren
iAmOren

Reputation: 2804

Edit:
Seems like my code is just like yours...
Anyways, I got 547.
The max will be solution[A.length-1][A.length-1].

Original Answer:
Here's what I got, using javascript (547) - I'm sure you can "translate" it to the language of your choice:

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

I've used console.table instead of console.log(JSON.stringify, but snippet doesn't support it.
I've logged the results of each step.
First, I created an array of same dimension filled with zeros.
Then, I've copied first column/row's value.
Then, I've populated the rest of the first row and first column by adding inputArray and left/up values.
Then, I've populated the rest of the matrix by adding inputArray and max of left/up.
Last column holds max values should you go off to the right, and last row - off the bottom.
Furthest corner will be the absolute max - and I've logged it.

Upvotes: 0

Related Questions