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 sum that can be generated from any path starting from any column in first row

Problem:

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.

Pseudo code:

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