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

Comments