Problem
Tommy and Bruiny are playing a turn-based game together. This game involves N marbles placed in a row. The marbles are numbered 0 to N-1 from the left to the right. Marble i has a positive value mi. On each player's turn, they can remove either the leftmost marble or the rightmost marble from the row and receive points equal to the sum of the remaining marbles' values in the row. The winner is the one with the higher score when there are no marbles left to remove.
Tommy always goes first in this game. Both players wish to maximize their score by the end of the game.
Assuming that both players play optimally, devise a Dynamic Program- ming algorithm to return the difference in Tommy and Bruiny's score once the game has been played for any given input. Your algorithm must run in O(N^2) time.
1) Define (in plain English) subproblems to be solved.
2) Write a recurrence relation for the subproblems
3) Using the recurrence formula in part b, write pseudocode to find the solution.
4) Make sure you specify
a) base cases and their values
b) where the final answer can be found
5) What is the complexity of your solution?