Input Matrix :
1 2 3
4 5 6
7 8 9
Output : 1 + 4 + 7 + 8 + 9 = 29
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.
Integer.MIN_VALUE
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;
}
}
Stack
to hold the traversal nodes : Deque stack = new LinkedList<>();
TravelNode
: stack.addFirst(new
TravelNode(0,0,0,grid))
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