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:

def findMaximumPath(mat):

rows = cols = len(mat)

count_list = []

for i in range(rows):

summ = 0

mat_index = [rows-1, cols-1]

curr_index = [0, i]

summ = mat[curr_index[0]][curr_index[1]]

while curr_index[0] != rows-1 and curr_index[1] != cols-1:

if mat[curr_index[0]][curr_index[1]+1] > mat[curr_index[0]+1][curr_index[1]]:

curr_index[1] = curr_index[1] + 1

else:

curr_index[0] = curr_index[0] + 1

summ += mat[curr_index[0]][curr_index[1]]

#print(str(curr_index) + " Sum: " + str(summ))

if curr_index[0] != rows-1 and curr_index[1] == cols-1:

for i in range(curr_index[0]+1, rows):

summ += mat[i][cols-1]

#print(str(i) + " Sum1: " +str(summ))

if curr_index[0] == rows-1 and curr_index[1] != cols-1:

for i in range(curr_index[1]+1, cols):

summ += mat[rows-1][i]

#print(str(i) + " Sum2: " +str(summ))

count_list.append(summ)

max_sum = max(count_list)

count = 0

for element in count_list:

if(element == max_sum):

count+= 1

print(count_list)

print("Maximum Sum: " + str(max_sum))

print("Number of Occurrences: " + str(count) + "\n")

mat1 = ([[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]])

mat2 = ([[1, 1, 1],

[2, 2, 2],

[3, 3, 3]])

findMaximumPath(mat1)

findMaximumPath(mat2)

Explanation:

Enjoy guys