Vankin's Mile is a solitaire game played by young wizards on an n x n square grid. The wizard starts by placing a token on any square of the grid. Then on each turn, the wizard moves the token either one square to the right or one square down. The game ends when the wizard 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 wizard starts with a score of zero; whenever the token lands on a square, the wizard adds its value to his score. The object of the game is to score as many points as possible, without resorting to magic.

For example, given the grid below, the wizard can score 8-6+7-3+4 = 10 points by placing the initial token on the 8 in the second row, and then moving down, down, right, down, down.

a. Given an algorithm to compute the max possible score for a game of Vankins Mile, given the n x n array of values as input.

b. Prove that your algorithm is correct.

c. Analyze your algorithms time and space requirements.

50739 06634 SS676 7-92-41 14577 -145) 77