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
- Define a recursive function
path_sum
that takes the matrix, the current rowi
, current columnj
, the current step countcount
, the total number of stepsk
, and the current sumsum
as parameters. - In the
path_sum
function: a. If the current position is(R-1, C-1)
and the step count equalsk
, update theoutput
with the maximum ofoutput
andsum
. b. Ifi
is within the valid range[0, R-1]
andj
is within the valid range[0, C-1]
, make two recursive calls:- Move rightwards: Call
path_sum
with incrementedj
andcount
, and updatedsum
withmatrix[i][j]
. - Move downwards: Call
path_sum
with incrementedi
andcount
, and updatedsum
withmatrix[i][j]
.
- Move rightwards: Call
- Define the
max_path_sum
function that initializes theoutput
with a minimum value. - Call the
path_sum
function frommax_path_sum
with initial parameters(0, 0, 0, R+C-1, 0)
. - 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 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;
}
Output
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);
}
}
Output
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;
}
Output
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);
}
}
Output
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();
Output
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();
Output
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()
Output
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()
Output
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);
}
}
Output
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();
Output
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);
}
Output
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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment