Given an **m x n** matrix filled with **non-negative** integers, use depth first search to find the maximum sum along a path from the top-left of the grid to the bottom-right. Return this maximum sum. The direction of movement is limited to right and down.

**Example:**

**Note:**

This problem has a more efficient solution based on Dynamic Programming techniques. We'll be exploring those in future problems - so don't fret just yet!

Input Matrix :

2 31

4 5 6

7 89

Output : 1 + 4 + 7 + 8 + 9 = 29

This problem has a more efficient solution based on Dynamic Programming techniques. We'll be exploring those in future problems - so don't fret just yet!

Need a **hand?** Try out these hints, one at a time.

This is a classic Depth First Search problem, and can be solved recursively or iteratively. BFS and DFS are slightly easier to visualize if coded iteratively - and for the subsequent hints, we'll be using a

`Stack`

to perform a classic `DFS`

for this problem. Since we need to preserve some information as we build our stack (i.e. the sum), we'll create a `local class`

- `TravelNode`

that stores row and column information of that particular number in the grid, along with the sum up till that point.
1) Initialize the maximum sum to

2) Create a local class

3) Create a

4) Enqueue the first

5) Loop in a while loop until the stack becomes empty. At each step, check if you've reached the bottom right node. If true, compare the

`Integer.MIN_VALUE`

2) Create a local class

`TravelNode`

to store the traversals on the stack : class TravelNode {

int row;

int col;

int nodeSum;

TravelNode(int r, int c, int sum, int[][] grid) {

row = r;

col = c;

sum += grid[r][c];

nodeSum = sum;

}

}

3) Create a

`Stack`

to hold the traversal nodes : `Deque` stack = new LinkedList<>();

4) Enqueue the first

`TravelNode`

: `stack.addFirst(new`

`TravelNode(0,0,0,grid))`

5) Loop in a while loop until the stack becomes empty. At each step, check if you've reached the bottom right node. If true, compare the

`sum`

stored in the `TravelNode`

with the `maxSum`

, and if it is greater, replace maxSum with that value. If the popped node is not the bottom right node, push the bottom and right numbers on (if within the matrix bounds) to the stack.
public static int matrixMaxSumDfs(int[][] grid) { }

**C**

**Java**

**Python**