Details: http://codingdragon.tumblr.com/post/65793702921/optimal-strategy-for-a-game

MaxPossibleSum.cpp

#include <iostream>
#include <vector>
using namespace std;

int Max(int a, int b){
    return a>b?a:b;
}

int Min(int a, int b){
    return a<b?a:b;
}

//V[i] => Value of ith vount from the left
//M[i][j] => Maximum Possible Amount that a player can win for coins V[i],V[i+1],....V[j]
int maxScore(vector<int> V){
	int M[V.size()][V.size()];
    
    //Initialize matrix, diagonal elements are populated first
	for(int i=0;i<V.size();i++){
		M[i][i] = V[i];
		if(i<V.size()-1) M[i][i+1] = Max(V[i],V[i+1]);
    }
    
    for(int i=2;i<V.size();i++){
        for(int j=0;j<V.size()-i;j++){
            M[j][j+i] = Max( V[j] + Min(M[j+2][j+i], M[j+1][j+i-1]), V[j+i] + Min(M[j+1][j+i-1], M[j][j+i-2]));
        }
    }
    
    
    return M[0][V.size()-1];
}

//Testing code
int main(int argc, const char * argv[])
{

    vector<int> piles={1,6,12,2,11,10};
    cout<<maxScore(piles);
    return 0;
}