# Maximum sum path in a matrix from top to bottom

An easy way to do this is with a Queue.

1. Add the first row
2. for every item in the queue, add any other valid moves
3. when finished, check if it’s a valid combination
4. check against the last highest

It uses an and Iterator method, Linq, and queues to return current best finds. What I suggest you do, is research the parts involved, step through it and inspect variables, use `Console.WriteLine` to look at what is happening. If you are really stuck you can always ask further questions about this code and what it’s doing.

The idea of the queue is, we add each element in the first row as initial items in the queue (that is our precondition by the rules you have given), then we go and look at the first element in the queue, then from that position (x,y) we go through all the next positions in the next row that we can legitimately visit. The queue also hold a list of columns visited and a value at that position. It could be done differently. I.e we really only need to to know the sum of all elements visited and a list of columns etc so we can validate the path afterwards.

Note : This is not the most optimal solution and it could be done a lot more efficiently and in less code in many other ways (and more elegantly). However, it touches on a lot of common concepts that are worth understanding

Given

``````private static Random _rand = new Random();

// this could be done with linq, however it's easy to see how it works
private static bool IsPathValid(int length, List<int> path)
{
for (var i = 0; i < length; i++)
if (!path.Contains(i))
return false;
return true;
}
``````

Iterator

``````public static IEnumerable<IEnumerable<(int col, int value)>> FindPath(int[, ] matrix)
{
var queue = new Queue<(int x, int y, List<(int col, int value)> path)>();
// add the first row to the queue
for (var i = 0; i < matrix.GetLength(1); i++)
queue.Enqueue((i, 0, new List<(int col, int value)>()));
// lets keep the higest found
var highest = int.MinValue;
// loop all queue items until none left
while (queue.Any())
{
// get the next item out of the queue
var(x, y, path) = queue.Dequeue();
// add the path we are visiting
path.Add((x, matrix[y, x]));
// if we have looked at all the rows, then time to return
if (y + 1 == matrix.GetLength(0))
{
// get a list of columns visited
var cols = path.Select(x => x.col).ToList();
// check to see if all columns are visited
if (IsPathValid(matrix.GetLength(1), cols))
{
var sum = path.Sum(x => x.value);
// sum the path, if it's not the highest we don't care
if (sum > highest)
{
// we are the highest path so far so let's return it
yield return path;
highest = sum;
}
}

continue;
}

// where ever we are, lets look at all the valid x's in the next row
var start = Math.Max(0, x - 1);
var finish = Math.Min(matrix.GetLength(1) - 1, x + 1);
// add them to the queue
// we inefficiently create a new path, as list is a reference type and we don't want to reuse it
for (var newX = start; newX <= finish; newX++)
queue.Enqueue((newX, y + 1, new List<(int col, int value)>(path)));
}
}
``````

Usage

``````// create a random matrix, make sure there the dimensions are going to produce a result
var y = _rand.Next(2, 5);
var matrix = new int[_rand.Next(y, y + 3), y];

// fill and print the matrix
Console.WriteLine("Matrix");
Console.WriteLine();
for (var i = 0; i < matrix.GetLength(0); i++)
{
for (var j = 0; j < matrix.GetLength(1); j++)
{
matrix[i, j] = _rand.Next(0, 20);
Console.Write(matrix[i, j].ToString().PadLeft(3));
}

Console.WriteLine();
}

Console.WriteLine();
Console.WriteLine("Best Path (column,Value)");
Console.WriteLine();

// get the best, which be the last
var best = FindPath(matrix).Last();
foreach (var item in best)
{
Console.WriteLine(item);
}

// show the result
Console.WriteLine();
Console.WriteLine("= " + best.Sum(x => x.value));
``````

Output

``````Matrix

14  9 17  0
19  5 11 10
17 12  9 13
3 11  2  5
0  0 12 15

Best Path (column,Value)

(0, 14)
(0, 19)
(1, 12)
(2, 2)
(3, 15)

= 62
``````

Full Demo Here

Additional Resources

CLICK HERE to find out more related problems solutions.

Scroll to Top