Question

Problem:-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

Matrix

Explanation:

Maximum path will be the sum starting from the cell of 0-th row and ending with cell of (n-1)th row.

Given a N *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.

Example:

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