Maximum sum path in a matrix from top to bottom

Question

Consider a n*m matrix. Suppose each cell in the matrix has a value assigned. We can start from each cell in first row in matrix. The allowed moves are diagonally left, downwards or diagonally right, i.e, from location (i, j) next move can be (i+1, j), or, (i+1, j+1), or (i+1, j-1). (If index is not outside the bounds of the array of course)

Let an additional restriction be added: only paths are allowed that pass (at least once) through all the columns.

Find the maximum sum of elements satisfying the allowed moves. For example for matrix:

The sum is equal:

Because the path is 15+5+2+6=28.

The main feature is that I need to use a dynamic approach. For a task without restriction about all the columns I could do:

            var matrix = new int[,]{ { 1, 15, 2 }, //start matrix
                                     { 9, 7, 5 },
                                     { 9, 2, 4},
                                     { 6, 9, -1 } };
            long n = matrix.GetLength(0);
            long m = matrix.GetLength(1);
            
            var sum = new List(); // list [n][m] of maxsums 
            for (int i = 0; i < n; i++)
            {
                sum.Add(new long[m].Select(e => e = long.MinValue).ToArray());
            }
            for (int i = 0; i < m; i++)
            {
                sum[0][i] = matrix[0, i]; //sums at first line equal first line in matrix
            }

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (j > 0) sum[i + 1][j - 1] = Math.Max(sum[i][j] + matrix[i + 1, j - 1], sum[i + 1][j - 1]); // diagonally left
                    sum[i + 1][j] = Math.Max(sum[i][j] + matrix[i + 1, j], sum[i + 1][j]); // downwards
                    if (j < m - 1) sum[i + 1][j + 1] = Math.Max(sum[i][j] + matrix[i + 1, j + 1], sum[i + 1][j + 1]); //diagonally right
                }
            }
           
            long max = sum[(int)n - 1].Max(); //maximum sum among all paths (answer)

And for the same matrix the maximum sum will equal:

Because the path is 15+9+9+9=42

Нow I can calculate a dynamics matrix for all paths and sums with restriction?

TheGeneral · Accepted Answer

An easy way to do this is with a Queue.

Add the first row
for every item in the queue, add any other valid moves
when finished, check if it's a valid combination
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 path)
{
    for (var i = 0; i < length; i++)
        if (!path.Contains(i))
            return false;
    return true;
}

Iterator

public static IEnumerable> 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

Maximum sum path in a matrix from top to bottom

Answers (1)

Related Questions