Given a square matrix of integers, find the maximum sum of elements on the way from the top-left cell to the bottom-right cell. From a given cell, you may only move either to the cell to the right or to the cell below. For example, consider the following matrix.

1 2 3
4 5 6
7 8 9

The maximum sum is 29 and is given by the following path.

 1    2    3
|
v
4 5 6
|
v
7 -> 8 -> 9

Your task is to write procedure traverse that takes a square matrix of integers and returns the corresponding answer.

Solution

Here is a Ruby implementation.

def traverse m
n = m.length - 1
(0..n).each do |i|
(0..n).each do |j|
u = if i > 0 then m[i-1][j] else 0 end
l = if j > 0 then m[i][j-1] else 0 end
m[i][j] = [u, l].max + m[i][j]
end
end
return m[-1][-1]
end

Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments