solution - Google Interview Question - 16th Feb 2011

O(n^2) solution:
f[i][j] = sum[i][j] + max(a[i]-f[i+1][j],a[j]-f[i][j-1])
f[i][i] = a[i];


#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXPOT 1000
int optA[MAXPOT*MAXPOT];
int flag[MAXPOT*MAXPOT];
int optimal_a(int* coin,int first,int last,int numPots)
{
    if(flag[first * numPots + last] == 1)
    {
          return optA[first * numPots + last];
    }
    if(first == last)
    {
             optA[first * numPots + last] = coin[first];
             flag[first * numPots + last] = 1;
             return coin[first];
    }
    if(last < first)return 0;
    int val1,val2;
    val1= coin[first] - optimal_a(coin,first+1,last,numPots);
    val2= coin[last] - optimal_a(coin,first,last-1,numPots);
    return max(val1,val2);
}
int main()
{
    int numPots;
    cin>>numPots;
    int coin[numPots];
    memset((void*)flag,0,MAXPOT*MAXPOT*sizeof(int));
    for(int i = 0 ;i<numPots;i++)
            cin>>coin[i];
    cout<<optimal_a(coin,0,numPots-1,numPots)<<endl;
           
    return 0;
}

Google Interview Question 16th Feb 2011

Given N pots arranged in a line. Each pot contains some gold coins. Two players A & B start playing a game in which each player will choose a pot alternatively. The constraint is that they can choose the pots at the beginning of the line or at the end of line (The pot once picked is removed from the line). The player which has more number of coins at the game wins, assuming A starts the game. Both player make optimum choice.
Example
N=4 (5,20, 4,1) --> A wins
N=5 (5,5, 20, 1, 1) --> B wins
N=5  (5 5 20 8 14) --> A wins

N=5  (5 5 20 1 14) --> B wins


Solution