#include<iostream>

using namespace std;

class Game {

public:

Game (int M[], int n);

int maxWin(int i, int j);

private:

int LookUp[10][10]; // Assumes line of money no more than 10
int V[10];
int l;
};

Game::Game (int M[], int n):l(n) {
for (int i = 0; i < n ; i++)
  V[i]= M[i];
  
for(int i= 0; i < n; i++)
  for (int j= 0; j< n; j++)  
    LookUp[i][j]= -1;
  
for (int i = 0; i < n ; i++)
  LookUp[i][i]= 0;
// Player 2 picks up the last piece  
  
for(int i= 0; i < n-1; i++) {
  if (M[i] > M[i+1]) LookUp[i][i+1]= M[i];
  else LookUp[i][i+1]= M[i+1]; 
 } // lines of length 2: Player 1 goes first
}

int Game::maxWin(int i, int j) {
// This complexity is O(n^2)
  if(j < i || j >=l || j < 0) return 0; // Invalid games
  if (LookUp[i][j] != -1) return LookUp[i][j]; // Already computed the answer
  else { // Otherwise compute it
    int minab;
    int a= maxWin(i+1, j-1) + V[i];
    int b= maxWin(i+2, j) + V[i];
      if (a > b) minab= b; 
      else minab= a;
    int mincd;  
    int c= maxWin(i,j-2) + V[j];
    int d= maxWin(i+1,j-1) + V[j];
     if (c > d) mincd= d; 
      else mincd= c;
    if (mincd < minab) {LookUp[i][j]= minab; return minab;} 
    else {LookUp[i][j]= mincd; return mincd;} 
      
  }
  
}

int main () {

int A[]= {8, 4, 1, 6, 4, 5};

Game line(A, 6);

cout << "Maximum winnings of Player 1 is ... " <<  line.maxWin(0, 5) << endl;
    
    
}