Question

Consider there is a row of n coins and you and a friend are playing a game (note: n is even). On your turn you can pick either the left most or the right most coin. Once you take a coin, a new coin is exposed. You have perfect information about what coins are available. Design an algorithm which gets you the maximum amount of money possible. Assume your friend is as clever as you are.

Answer 1

TO FIND THE MAXIMUM AMOUNT OF MONEY POSSIBLE:

int maxLoot(int *hval, int n)

{

    if (n == 0)

        return 0;

    if (n == 1)

        return hval[0];

    if (n == 2)

        return max(hval[0], hval[1]);

// dp[i] represent the maximum amount of money

int dp[n];

// Initialize the dp[0] and dp[1]

    dp[0] = hval[0];

    dp[1] = max(hval[0], hval[1]);

// Fill remaining positions

    for (int i = 2; i<n; i++)

        dp[i] = max(hval[i]+dp[i-2], dp[i-1]);

return dp[n-1];

}