Coin in Line

/***

There are n coins in a line. (Assume n is even). Two players take turns to take a coin

from one of the ends of the line until there are no more coins left. The player with the

larger amount of money wins.

Would you rather go first or second? Does it matter?

Assume that you go first, describe an algorithm to compute the maximum amount of money

you can win.

eg.

int a[] = { 3, 2, 2, 3, 1, 2 }

Note:

1. array is unsorted

2. the guaranteed win strategy

compute the sum of odd and the sum of even (the index of coin)

if even > odd, every round, only picked the even coin

otherwise, only picked the odd coin

3. the maximum amount of money you can win (different with 2.)

Recursive, consider the way to compute subset sum

http://leetcode.com/2011/02/coins-in-line.html

***/

#include<iostream>

using namespace std;

int maxWin(int *a, int index_x, int index_y, int sum) {

       //base case

       if(index_x == index_y) {

              return a[index_x] + sum;

       }

       if(index_x > index_y) return sum;

       return max(max(maxWin(a, index_x+2, index_y, sum+a[index_x]),maxWin(a, index_x+1, index_y-1, sum+a[index_x])),

                  max(maxWin(a, index_x+1, index_y-1, sum+a[index_y]),maxWin(a, index_x, index_y-2, sum+a[index_y])));

}

void main() {

       int a[] = { 3, 2, 2, 3, 1, 2 };

       int sz = sizeof(a) / sizeof(int);

       cout<<maxWin(a, 0, sz-1, 0)<<endl;

}