1) Initialize the maximum sum to
Integer.MIN_VALUE2) 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.
