Two players X and Y are playing a game in which there are pots of gold arranged in a line, each containing some gold coins. They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player who has a higher number of coins at the end. The objective is to maximize the number of coins collected by X, assuming Y also plays optimally.
Return the maximum coins X could get while playing the game. Initially, X starts the game.
- Time : O(n^2)
- Space : O(n^2)
1 | class Solution { |