Jesse and Russell found a pile of money and want to split it up amongst them. They decide to play a strategy game using the money, so that the smarter of them gets to keep the most. Heres how the game works:

There are n bills of various denominations and we line them up in a list S[1..n] so the ith bill has value S[i]. On a players turn, they may take either the first bill or the last bill in the list, and then it becomes the other players turn. The goal is to collect as much money as possible

Russell wants to play this game optimally, so hes asking you to design an algorithm that computes an optimal strategy. Your job is to (1) design an O(n2) time algorithm that given the list S[1..n] precomputes some information to give to Russell before the game, and (2) an O(1) time algorithm that given a configuration of the game and the precomputed information, identifies the best move.