❔ Maximum path sum in matrix
Given a M x N grid filled with some values I need to find a path from a target node which maximizes the sum of all values along its path.
I can move in any direction. How can I do this? I've found some solutions online but they all go only from the top row to the bottom row when I need to go in all directions from any node.
50 Replies
also there is a max length of the path
What do you have so far?
not much, can't figure out how to do this
There might exists some clever algorithm or heuristic to find the 100% correct path. But if you have no clue on how to go about it, you should start with the easiest solution
Which would be: Just try out every path and track the one with the highest sum 😄
that wont work
my grid is huge
and max lenght of the path ranges from 50 to 100
so bruteforcing it wont work
Hmm, then that seems like something that dynamic programming could solve 
lemme think
So here's what I think:
We start with finding the max sum path for length 1
Which is just the maximum value of the grid
Ah, question: Does any direction include diagonally?
lemme think
So here's what I think:
We start with finding the max sum path for length 1
Which is just the maximum value of the grid
Ah, question: Does any direction include diagonally?yep
Then you check all 8 neighbours of that cell. You take the neighbour with the highest value to get the max sum path of length 2.
This is the first thing that came into my mind. Pretty sure this approach wouldn't work if e.g. the max value of the grid is 10, this is surrounded by 1's and everything else is a 9. And we try to get a path length of 2
But maybe we can work from there
i was thinking about using breadth first search algorithm
what u described would fail in this scenario
if path length = 2
then it will go from yellow to 1 and then to the next 1
But the max is 9, so my approach would start there
nah, we dont start from the highest value
we start from a predefined cell
so in this example grid[2,2]
Oh, i thought we just need to find the max sum path
nope
yeah, i didnt say it earlier, mb
You should add this to the description then 😄
one sec
I suppose the conditions are set in a way that you can find the max sum path guaranteed?
wdym?
Because if we take your example, then what would happen if the path length doesn't reach the outer ring of the matrix.
yeah, dont worry about that
Aight
Okay so
What’s the goal
When does the path start and stop
Is there a predetermined length or you’re going from the top left to the bottom right
when path reaches
n lengthSo you have a given starting point right? And you want to look for the biggest number possible in any path starting from it with length of n
Sounds like dynamic programming
exactly
Because you’d have to explore all possible paths and then return the biggest of them all
Can you provide an illustration of the problem?
let me draw one ;p
one sec
so max length of the path = 6
so this path's value = 18
and this path's value = 21
so thats the best path for this given grid and path length
So the initial cell doesn’t contribute to the count?
And you said maximum path, that makes me curious, can negative numbers be included here?
nope, cell's value is a random int from 0 to 100
nope
but i guess if it would make the problem easier then we can give the initial cell a value of 1 and make it contribute to the count
I don’t think it’d change anything, I just asked because if it counted then the length would be 7 for each path instead of 6
👍
Okay so what solution/approach do you have in mind already
none right now, I had a few ideas but i dropped them cuz they would be just too slow
I think with how non-restrictive this problem is that may not be unavoidable
The issue is that your movement is not restricted, you could move in any direction whatsoever, that also means considering a single path you have to be aware of the cells you already hit
Usually you’d start from the top left and they’d say some shit like you can only move right or down. I’m not saying this isn’t unsolvable but you may have to sacrifice speed here
okay so just a random idea
but what if we would divide the grid into 4 parts
something like this
and for each part
lets say, top right one
we find a max value in it which is 9
and then
from the max value to the origin point we create this "sub grid"
and then we try to find the best path from bottom left corner to the top left corner
with only possible moves being up, right, up-right
well, we wont be able to find 100% best path but i think that will be enough for my project
GeeksforGeeks
Maximum sum path in a matrix from top-left to bottom-right - Geeksf...
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
and we would do this for each of these 4 parts
@moooodie
Uh
The link you posted is a different thing no?
That’s from top left to bottom right
How would doing it for each grid work
yep
i would use it for the sub grid
this thingy
Yeah but how would that get you to your answer
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.