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.

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

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.

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.