Vankin’s Mile is a solitaire game played on an n x n square grid. The player starts by placing a token on any square of the grid. Then on each turn, the player moves the token either one square to the right or one square down. The game ends when player moves the token off the edge of the board. Each square of the grid has a numerical value, which could be positive, negative, or zero. The player starts with a score of zero; whenever the token lands on a square, the player adds its value to his score. The object of the game is to score as many points as possible.
Describe and analyze an efficient algorithm to compute the maximum possible score for a game of Vankin’s Mile, given the nx n array of values as input.