largest sum of any of the paths till last row

Interview Practice Questions: There is a N*N integer matrix Arr[N][N]. From the row r and column c, we can go to any of the following three indices: (r+1,c-1), (r+1,c) or (r+1,c+1). Find the maximum s

There is a N*N integer matrix Arr[N][N]. From the row r and column c, we can go to any of the following three indices:

I.                Arr[ r+1 ][ c-1 ] (valid only if c-1>=0)
II.               Arr[ r+1 ][ c ]
III.              Arr[ r+1 ][ c+1 ] (valid only if c+1<=N-1)
So if we start at any column index on row 0, what is the largest sum of any of the paths till row N-1.

Solution

Solution below is O(n^2) solution. We will update all array entries. Starting from last row and moving till first row. Each array entry will be maximum sum that can be generated when starting from that point. At the end we will find entry in first row that has maximum value.

void calculateSum(int[][] a,int n,int row) {
       if(row == n-1) {
           return;
       }
       calculateSum(a,n,row+1);
       for(int j=0;j<n;j++) {
           // calculate a[row][j]
           int max = a[row+1][j];
           if(j-1 >=0 && a[row+1][j-1] > max) {
                 max = a[row+1][j-1];
           }
           if(j+1 <= n-1 && a[row+1][j+1] > max) {
                 max = a[row+1][j+1];
           }
           a[row][j] += max;
        }
 }

void maxSumPath(int[][] a,int n) {
      calculateSum(a,n,0);
      int max = a[0][0];
      for(int j=1;j<n;j++) {
          if(a[0][j] > max)max = a[0][j];
      }
      System.out.println(max);
} 

Read full article from Interview Practice Questions: There is a N*N integer matrix Arr[N][N]. From the row r and column c, we can go to any of the following three indices: (r+1,c-1), (r+1,c) or (r+1,c+1). Find the maximum s