Question

You will be given a square matrix of N rows and N columns (1 == N<= 1000) containing positive and negative integers with absolute value not larger than 1000. You are required to compute the greatest sum achievable by walking a path, starting at any cell of the matrix and always moving downwards or rightwards. Additionally, you have to report the number of times that value is achievable. N will be in the first line of the input. N lines follow with N integers each. You should output a single line with two integers separated by a single blank space: first one is the greatest sum, second one is the number of times this value can be reached.
Case 1:
For the input provided as follows:
5
3 1 -2 1 1
-6 -1 4 -1 -4
1 1 1 1 1
2 2 2 2 2
1 1 1 1 1
Output of the program will be:
15 1
Case 2:
For the input provided as follows:
3
1 1 1
2 2 2
3 3 3
Output of the program will be:
12 1

Answer 1

Answer:

Maximum path sum that starting with any cell of 0-th row and ending with any cell of (N-1)-th row

Given a N X N matrix Mat[N][N] of positive integers. There are only three possible moves from a cell (i, j)

(i+1, j)

(i+1, j-1)

(i+1, j+1)

Starting from any column in row 0, return the largest sum of any of the paths up to row N-1.

Examples:

Input : mat[4][4] = { {4, 2, 3, 4},

{2, 9, 1, 10},

{15, 1, 3, 0},

{16, 92, 41, 44} };

Output :120

path : 4 + 9 + 15 + 92 = 120