Maximum sum path in a Matrix

The problem involves finding the maximum sum path in a matrix from the top-left corner (0, 0) to the bottom-right corner (R-1, C-1). Each step in the path can only move either rightwards or downwards. The goal is to find the path that maximizes the sum of the elements along the way.

Example

Consider the following matrix:

4  6  -2  2
3  -1  5   3
1  7   4   6

The maximum sum path in this matrix is 4 -> 6 -> -1 -> 7 -> 4 -> 6, and the sum of these elements is 4 + 6 - 1 + 7 + 4 + 6 = 26.

Idea to Solve the Problem

To find the maximum sum path, we can use a recursive approach. Starting from the top-left corner (0, 0), we can explore two options: moving rightwards or moving downwards. We will continue this exploration recursively until we reach the bottom-right corner (R-1, C-1). During this process, we will keep track of the sum of elements along the path and update the maximum sum whenever we find a new path with a greater sum.

Algorithm

1. Define a recursive function path_sum that takes the matrix, the current row i, current column j, the current step count count, the total number of steps k, and the current sum sum as parameters.
2. In the path_sum function: a. If the current position is (R-1, C-1) and the step count equals k, update the output with the maximum of output and sum. b. If i is within the valid range [0, R-1] and j is within the valid range [0, C-1], make two recursive calls:
   • Move rightwards: Call path_sum with incremented j and count, and updated sum with matrix[i][j].
   • Move downwards: Call path_sum with incremented i and count, and updated sum with matrix[i][j].
3. Define the max_path_sum function that initializes the output with a minimum value.
4. Call the path_sum function from max_path_sum with initial parameters (0, 0, 0, R+C-1, 0).
5. Print the output.

Pseudocode

path_sum(matrix, output, i, j, count, k, sum):
    if (i, j) is (R-1, C-1) and count == k:
        update output with maximum of output and sum
    else if i is within [0, R-1] and j is within [0, C-1]:
        // Move rightwards
        call path_sum with incremented j, count, and sum + matrix[i][j]
        // Move downwards
        call path_sum with incremented i, count, and sum + matrix[i][j]

max_path_sum(matrix):
    initialize output as INT_MIN
    call path_sum with initial parameters (0, 0, 0, R+C-1, 0)
    print output

main:
    matrix = ...  // Define the matrix
    max_path_sum(matrix)

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// C Program
// Maximum sum path in a Matrix
#include <stdio.h>
#include <limits.h>

#define R 3 
#define C 4 

// Find the path sum of (0,0) to Matrix (R-1,C-1) 
void path_sum(int matrix[R][C],int *output,int i ,int j,int count,int k,int sum)
{

  if(count==k && *output < sum)
  {
    // When get a new result
    *output = sum;
  }
  else if(i < R && j < C)
  {
    //Recursive execute method with new parameters
    path_sum(matrix,output,i+1,j,count+1,k,sum+matrix[i][j]);
    path_sum(matrix,output,i,j+1,count+1,k,sum+matrix[i][j]);
  }
}

// Handles the request to find max path sum in a matrix
void max_path_sum(int matrix[R][C])
{
    // Set initially min value
    int output = INT_MIN;

    // Calculate max path sum
    path_sum(matrix,&output,0,0,0,R+C-1,0);

    // Display find result
    printf(" %d \n",output);
}

int main()
{
    int matrix[R][C] =
    {
        {4, 6, -2 , 2 },
        {3, -1, 5 , 3 },
        {1, 7,  4,  6 }
    };
    // 4 -> 6 -> -1 -> 7 -> 4 -> 6
    max_path_sum(matrix);

  return 0;
}

 26

/*
    Java program 
    Maximum sum path in a Matrix
*/
// Define TreeNode
public class MyMatrix
{
    public int output;
    // Find the path sum of (0,0) to Matrix (R-1,C-1) 
    public void path_sum(int[][] matrix, 
  	int i, int j, 
  	int count, int k, 
  	int sum, 
  	int rows, int cols)
    {
        if (count == k && this.output < sum)
        {
            // When get a new result
            this.output = sum;
        }
        else if (i < rows && j < cols)
        {
            //Recursive execute method with new parameters
            path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j],rows,cols);
            path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j],rows,cols);
        }
    }
    // Handles the request to find max path sum in a matrix
    public void max_path_sum(int[][] matrix)
    {
        int r = matrix.length;
        int c = matrix[0].length;
        // Set initially min value
        this.output = Integer.MIN_VALUE;
        // Calculate max path sum
        path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
        // Display find result
        System.out.print("  " + this.output + " \n");
    }
    public static void main(String[] args)
    {
        MyMatrix obj = new MyMatrix();
        int[][] matrix =
        {
            {
                4 , 6 , -2 , 2
            }, 
            {
                3 , -1 , 5 , 3
            }, 
            {
                1 , 7 , 4 , 6
            }
        };
        // 4->6->-1->7->4->6
        obj.max_path_sum(matrix);
    }
}

  26

// Include header file
#include <iostream>
#include<limits.h>
#define R 3 
#define C 4 
using namespace std;
/*
    C++ program 
    Maximum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	public: int output;
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	void path_sum(int matrix[R][C], int i, int j, int count, int k, int sum)
	{
		if (count == k && this->output < sum)
		{
			//  When get a new result
			this->output = sum;
		}
		else if (i < R && j < C)
		{
			// Recursive execute method with new parameters
			this->path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j]);
			this->path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j]);
		}
	}
	//  Handles the request to find max path sum in a matrix
	void max_path_sum(int matrix[R][C])
	{

		//  Set initially min value
		this->output = INT_MIN;
		//  Calculate max path sum
		this->path_sum(matrix, 0, 0, 0, R + C - 1, 0);
		//  Display find result
		cout << "  " << this->output << " \n";
	}
};
int main()
{
	MyMatrix obj = MyMatrix();
	int matrix[R][C] = {
		{
			4 , 6 , -2 , 2
		} , {
			3 , -1 , 5 , 3
		} , {
			1 , 7 , 4 , 6
		}
	};
	//  4->6->-1->7->4->6
	obj.max_path_sum(matrix);
	return 0;
}

  26

// Include namespace system
using System;
/*
    C# program 
    Maximum sum path in a Matrix
*/
//  Define TreeNode
public class MyMatrix
{
	public int output;
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	public void path_sum(int[,] matrix, int i, int j, int count, int k, int sum, int rows, int cols)
	{
		if (count == k && this.output < sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i,j], rows, cols);
			path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i,j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	public void max_path_sum(int[,] matrix)
	{
		int r = matrix.GetLength(0);
		int c = matrix.GetLength(1);
		//  Set initially min value
		this.output = int.MinValue;
		//  Calculate max path sum
		path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		Console.Write("  " + this.output + " \n");
	}
	public static void Main(String[] args)
	{
		MyMatrix obj = new MyMatrix();
		int[,] matrix = {
			{
				4 , 6 , -2 , 2
			} , {
				3 , -1 , 5 , 3
			} , {
				1 , 7 , 4 , 6
			}
		};
		//  4->6->-1->7->4->6
		obj.max_path_sum(matrix);
	}
}

  26

<?php
/*
    Php program 
    Maximum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	public $output;
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	public	function path_sum( & $matrix, $i, $j, $count, $k, $sum, $rows, $cols)
	{
		if ($count == $k && $this->output < $sum)
		{
			//  When get a new result
			$this->output = $sum;
		}
		else if ($i < $rows && $j < $cols)
		{
			// Recursive execute method with new parameters
			$this->path_sum($matrix, $i + 1, $j, $count + 1, $k, $sum + $matrix[$i][$j], $rows, $cols);
			$this->path_sum($matrix, $i, $j + 1, $count + 1, $k, $sum + $matrix[$i][$j], $rows, $cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	public	function max_path_sum( & $matrix)
	{
		$r = count($matrix);
		$c = count($matrix[0]);
		//  Set initially min value
		$this->output = -PHP_INT_MAX;
		//  Calculate max path sum
		$this->path_sum($matrix, 0, 0, 0, $r + $c - 1, 0, $r, $c);
		//  Display find result
		echo "  ". $this->output ." \n";
	}
}

function main()
{
	$obj = new MyMatrix();
	$matrix = array(
      array(4, 6, -2, 2), 
      array(3, -1, 5, 3), 
      array(1, 7, 4, 6)
    );
	//  4->6->-1->7->4->6
	$obj->max_path_sum($matrix);
}
main();

  26

/*
    Node Js program 
    Maximum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	path_sum(matrix, i, j, count, k, sum, rows, cols)
	{
		if (count == k && this.output < sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
			this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	max_path_sum(matrix)
	{
		var r = matrix.length;
		var c = matrix[0].length;
		//  Set initially min value
		this.output = -Number.MAX_VALUE;
		//  Calculate max path sum
		this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		process.stdout.write("  " + this.output + " \n");
	}
}

function main()
{
	var obj = new MyMatrix();
	var matrix = [
		[4, 6, -2, 2] , [3, -1, 5, 3] , [1, 7, 4, 6]
	];
	//  4->6->-1->7->4->6
	obj.max_path_sum(matrix);
}
main();

  26

import sys

#  Python 3 program 
#  Maximum sum path in a Matrix

#  Define TreeNode
class MyMatrix :
	
	#  Find the path sum of (0,0) to Matrix (R-1,C-1) 
	def path_sum(self, matrix, i, j, count, k, sum, rows, cols) :
		if (count == k and self.output < sum) :
			#  When get a new result
			self.output = sum
		
		elif(i < rows and j < cols) :
			# Recursive execute method with new parameters
			self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols)
			self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols)
		
	
	#  Handles the request to find max path sum in a matrix
	def max_path_sum(self, matrix) :
		r = len(matrix)
		c = len(matrix[0])
		#  Set initially min value
		self.output = -sys.maxsize
		#  Calculate max path sum
		self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c)
		#  Display find result
		print("  ", self.output ," \n", end = "")
	

def main() :
	obj = MyMatrix()
	matrix = [
		[4, 6, -2, 2] , 
        [3, -1, 5, 3] , 
        [1, 7, 4, 6]
	]
	#  4->6->-1->7->4->6
	obj.max_path_sum(matrix)

if __name__ == "__main__": main()

   26

#  Ruby program 
#  Maximum sum path in a Matrix

#  Define TreeNode
class MyMatrix  
	# Define the accessor and reader of class MyMatrix  
	attr_reader :output
	attr_accessor :output
 
	
	#  Find the path sum of (0,0) to Matrix (R-1,C-1) 
	def path_sum(matrix, i, j, count, k, sum, rows, cols) 
		if (count == k && self.output < sum) 
			#  When get a new result
			self.output = sum
		elsif(i < rows && j < cols) 
			# Recursive execute method with new parameters
			self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols)
			self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols)
		end

	end

	#  Handles the request to find max path sum in a matrix
	def max_path_sum(matrix) 
		r = matrix.length
		c = matrix[0].length
		#  Set initially min value
		self.output = -(2 ** (0. size * 8 - 2))
		#  Calculate max path sum
		self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c)
		#  Display find result
		print("  ", self.output ," \n")
	end

end

def main() 
	obj = MyMatrix.new()
	matrix = [
		[4, 6, -2, 2] , 
        [3, -1, 5, 3] , 
        [1, 7, 4, 6]
	]
	#  4->6->-1->7->4->6
	obj.max_path_sum(matrix)
end

main()

  26 

/*
    Scala program 
    Maximum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix(var output: Int)
{
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	def path_sum(matrix: Array[Array[Int]], 
      i: Int, j: Int, count: Int, k: Int, 
        sum: Int, rows: Int, cols: Int): Unit = {
		if (count == k && this.output < sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix(i)(j), rows, cols);
			this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix(i)(j), rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	def max_path_sum(matrix: Array[Array[Int]]): Unit = {
		var r: Int = matrix.length;
		var c: Int = matrix(0).length;
		//  Set initially min value
		this.output = Int.MinValue;
		//  Calculate max path sum
		this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		print("  " + this.output + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyMatrix = new MyMatrix(0);
		var matrix: Array[Array[Int]] = 
          Array(Array(4, 6, -2, 2), 
                Array(3, -1, 5, 3), 
                Array(1, 7, 4, 6));
		//  4->6->-1->7->4->6
		obj.max_path_sum(matrix);
	}
}

  26

/*
    Swift 4 program 
    Maximum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	var output: Int;
	init()
	{
		self.output = 0;
	}
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	func path_sum(_ matrix: [[Int]], _ i: Int, _ j: Int, _ count: Int, _ k: Int, _ sum: Int, _ rows: Int, _ cols: Int)
	{
		if (count == k && self.output < sum)
		{
			//  When get a new result
			self.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
			self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	func max_path_sum(_ matrix: [
		[Int]
	])
	{
		let r: Int = matrix.count;
		let c: Int = matrix[0].count;
		//  Set initially min value
		self.output = Int.min;
		//  Calculate max path sum
		self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		print("  ", self.output ," \n", terminator: "");
	}
}
func main()
{
	let obj: MyMatrix = MyMatrix();
	let matrix: [
		[Int]
	] = [
		[4, 6, -2, 2] , [3, -1, 5, 3] , [1, 7, 4, 6]
	];
	//  4->6->-1->7->4->6
	obj.max_path_sum(matrix);
}
main();

   26

/*
    Kotlin program 
    Maximum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	var output: Int;
	constructor()
	{
		this.output = 0;
	}
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	fun path_sum(matrix: Array < Array < Int >> , i: Int, j: Int, count: Int, k: Int, sum: Int, rows: Int, cols: Int): Unit
	{
		if (count == k && this.output < sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
			this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	fun max_path_sum(matrix: Array<Array<Int>> ): Unit
	{
		var r: Int = matrix.count();
		var c: Int = matrix[0].count();
		//  Set initially min value
		this.output = Int.MIN_VALUE;
		//  Calculate max path sum
		this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		print("  " + this.output + " \n");
	}
}
fun main(args: Array < String > ): Unit
{
	var obj: MyMatrix = MyMatrix();
	var matrix: Array <Array<Int>> = 
      arrayOf(arrayOf(4, 6, -2, 2), 
              arrayOf(3, -1, 5, 3), 
              arrayOf(1, 7, 4, 6));
	//  4->6->-1->7->4->6
	obj.max_path_sum(matrix);
}

  26

Output Explanation

The mentioned C code implements the above algorithm to find the maximum sum path in the matrix. It uses a recursive approach to explore all possible paths from the top-left corner to the bottom-right corner, updating the maximum sum whenever a new path with a greater sum is found. The output demonstrates the maximum sum path and the sum of elements along that path.

Time Complexity

The time complexity of the algorithm depends on the number of recursive calls made, which is proportional to the number of elements in the matrix. Therefore, the time complexity is O(R * C), where R is the number of rows and C is the number of columns in the matrix. This is because the algorithm explores all possible paths in the matrix.