![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645180244005-Article_418.png\")
<\/p>\n<\/p>\n
\nDynamic programming<\/p>\n<\/blockquote>\n
DIFFICULTY LEVEL:<\/h3>\n
\nMedium.<\/p>\n<\/blockquote>\n
PROBLEM STATEMENT
(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n\nAfter having lost to you again, your friend challenges you yet again for another round of Monopoly.
\nThis time, he changes the rules of the game slightly, hoping that this would throw you off your game and he would finally have his sweet revenge. Your task is to play optimally and win this, again!
\nThe updated rules are as follows :Consider a row of
\nN notes of values V1,V2…Vn, where N is even. We play a game against an opponent by alternating turns. In each turn, a player performs this operation K times: select either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin.
\nDetermine the maximum possible amount of money we can definitely win if we move first.<\/p>\n<\/blockquote>\nFor Example :<\/h4>\n
5 2\n2 7 9 4 4\n\nIn the first step, you take 2 and 7\nOpponent takes 9 and 4. \nYou take 4 at the end.\nSo total= 13. <\/code><\/pre>\nSOLVING APPROACH:<\/h3>\n
\nLet’s define a function f(st,end) where st is the starting index and end is the ending index available for the player to select coins.<\/p>\n
Now try to understand that from the given i and j(starting and ending index) we can easily figure out whose turn it is.<\/p>\n
sz=j-i+1;\ndiff=n-sz;\ndiff=diff\/k;<\/code><\/pre>\nNow ,if diff%2=0,it’s the turn of first player,else second player plays.<\/p>\n
Base case-<\/p>\n
if sz i.e. the available range is less than k,then add all the elements in the array.<\/p>\n
We have the maximise the sum if it’s the turn of first player and minimise if the it’s the turn of second player.<\/p>\n<\/blockquote>\n
You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.<\/h4>\n