Write a program to find the sum of the path which has the maximum length, given a square matrix.

Maximum path sum

Google is creating a toy robo can travel within a given square grid. Each cell in the grid has a number. To prove the intelligence of the company, Google decides to make the robo travel in a path which has the maximum sum when the number in the path are added.

To start with, the project manager has asked the programmers to fix the source as coordinate (0,0) and destination as coordinate (n-1,n-1), where 'n' is the size of the square grid. And also the robo can travel in only two directions, right, down and diagonally right, i.e., if the current position is (x,y), the robo's next move can be either (x+1,y), (x,y+1) or (x+1,y+1).

Write a program to find the sum of the path which has the maximum length, given a square matrix.

Sample Input:

4

1 4 5 21

3 22 1 5

22 21 1 6

3 32 2 2

Sample Output:

84

Explanation for the sample input and output:

This is the input matrix.

1	4	5	21
3	22	1	5
22	21	1	6
3	32	2	2

This is the path with maximum sum.

                                                                C-Solution

#include<stdio.h>
#include<stdlib.h>
int max(int x, int y, int z);
int maxSum(int cost[50][50], int m, int n)
{
 if (n < 0 || m < 0)
   return 0;
 else if (m == 0 && n == 0)
   return cost[m][n];
 else
   return cost[m][n] +

 max(maxSum(cost,m-1,n-1),maxSum(cost,m-1,n),maxSum(cost,m,n-1));
}

int max(int x, int y, int z)
{
   if (x > y)
      return (x > z)? x : z;
   else
      return (y > z)? y : z;
}

int main()
{
   int n,i,j;
   scanf("%d",&n);int a[50][50];
   for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        scanf("%d",&a[i][j]);
    printf(" %d ", maxSum(a,n,n));
   return 0;
}