Consider the maximum matrix traversal problem. Your input is an m × n matrix fil
ID: 3848703 • Letter: C
Question
Consider the maximum matrix traversal problem. Your input is an m × n matrix filled with integers, and the solution to the problem is the largest sum attainable by starting in the upper left of the matrix and adding either the element below or to the right, then repeating until you are in the lower right
For example, the solution for the 3 × 3 matrix below is 11 (0 + 8 + -2 + 4 + 1):
Give pseudocode for a greedy algorithm for this problem. Your algorithm should take O(n + m) time, though it is not required to be correct.
-10 . 041 523 086Explanation / Answer
The psedocode for the algorithm is as follows:
intialize i = 0; j = 0; sum = 0\ i and j are the indexes for row and column and the matrix is m x n
while (i < m-1 || j < n-1) {// till i and j reach m-1 and n-1
look at all the possible 7 possible neighbours from the location i and j leaving the neighbour from
where we have just moved. // every location will have at most 7 possible neighbours to be considered.The // neighbhours may be less than 7 dependeing on the current position of i and j
// for ex if i = 0 j = 1 , we will have 4 neighbours to be considered, leaving
// one neighbour from where we might have just moved.
choose the maximum (considering negative entities also) out the neighbours.
Add it to the sum
move to the choosen neighbour position (i.e update i and j with the position of new chosen neighbour)
continue the loop
}
print the sum
As every updation of i and j in the loop is happening either to the adjacent row or column, the total number of
transitions can not exceed m+n. hence the complexity of the above alogorithm is O(m+n).