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
 4    5    6
 7 -> 8 -> 9

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


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]
  return m[-1][-1]

Want to read more?

I love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. 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.