Consider an array of n coins with positive integer value and two players player1 and player2. Each player takes the coins turn after turn till there are coins left. The one with the
maximum value wins. The number of coins that a player can take is governed by a variable S initially =1, and a player can take the k coins starting from left contiguously where 1<=k
<=2*S And after a player takes say k coins the value of S becomes max(S,k). Also, there is an assumption that both players play the optimal strategy. We have to find the maximum amount of
coin value that player 1 can take in the game
For example: if the input is [3,6,8,5,4], the output should be 12 because if player1 takes one coin, player 2 takes 2 coins, and then player one retakes 2 coins. So player1
will have 3 5 4 = 12.
My Thoughts: I feel there could be some way to do it using dynamic programming, but I cannot find the subproblems or optimal substructure. The conditions look very complex. Any ideas on how to approach this?

CodePudding user response：

The sub problem is identified by:

• The number of coins already taken. Otherwise put: the index in the coins array from where the next coins can be taken.
• The value of S.

As the number of coins that can be taken and the value of S can never exceed the number of coins