Two players play a game where they start with a row of n pilesof varied amounts of money. The players take turns and in each turna player can pocket either the money in the first pile or the lastpile in the row of piles that remains. Design an efficientalgorithm (using dynamic programming), which on any given sequenceof amounts, determines the maximum amount of money that player 1can win.
If n is even, prove that player 1 wins at least half the moneyavailable. If n is odd, player 1 actually gets one more pile thanplayer 2. In spite of that, show with a simple example that player1 can be left with far less than half the total amount.
Note: you can write the algorithm either in plain English or inpseudocode.
