Q4:

You are given an n x n square matrix. Each cell contains a number (positive, negative, or zero); you may assume they are integers if that helps. Now you are thrown into one of the square cells. Your task is to escape the board and at the same time collect as much value as you can. Every time you reach a cell, you gain/lose by the amount stored in that cell.

From a cell, you can traverse to a cell below or to the right. You cannot skip cells while traveling to the right or down. So, from a cell, you can only move to the cell that is immediately to the right or immediately below. You can escape the board from the the right boundary or from the bottom, i.e., only from a cell in the bottom-most row or rightmost column.

Moreover, you cannot go back to a cell that you have already visited; otherwise, you can just keeping visiting two consecutive positive cells and obtain infinite value, yet never escaping - you are filthy rich but alone forever!

Give an algorithm to escape as rich as you can be. State the complexity. Your explanation/pseudo-code should be very clear. You also need to provide substantial reasoning as to why your algorithm should work.