Consider there is a row of n coins and you and a friend areplaying a game (note: n is even). On your turn you can pick eitherthe left most or the right most coin. Once you take a coin, a newcoin is exposed. You have perfect information about what coins areavailable. Design an algorithm which gets you the maximum amount ofmoney possible. Assume your friend is as clever as you are.
Answer
TO FIND THEMAXIMUM AMOUNT OF MONEY POSSIBLE:
int maxLoot(int *hval, int n)
{
if (n == 0)
return 0;
if (n == 1)
returnhval[0];
if (n == 2)
returnmax(hval[0], hval[1]);
// dp[i] represent the maximum amount of
OR
OR