title: How to design strategy and algorithm for gold box game
body: <blockquote>
  <p>Gold box problem (Approach)</p>
  <p>There are ‘n’ gold boxes placed in a row, each having different number of gold coins.</p>
  <p>2 players play a game, where the motive is to collect the maximum number of gold coins. Each player can see how many coins are present in each box, but can get a box from either end only, on his turn.
  Design a strategy such that Player1 wins (Assuming both players play smartly)</p>
  </blockquote>
  <p>This problem was asked in an Amazon interview. I tried this approach:</p>
  <pre><code>#include&lt;stdio.h&gt;
  int max(int a, int b) {
      return a&gt;b?a:b;
  }
  int maxCoins(int arr[], int i, int j, int turn) {
      if(i==j) {
          if(turn == 1) return arr[i];
          else return 0;
      }
      if(turn) {
          return max(arr[i] + maxCoins(arr,i+1,j,0),arr[j] + maxCoins(arr,i,j-1,0));
      } else {
          if(arr[i]&gt;arr[j])
          return maxCoins(arr,i+1,j,1);
          else
          return maxCoins(arr,i,j-1,1);
      }
  }    
  int main() {
      int arr[10] = {6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
      printf(&quot;%d\n&quot;,maxCoins(arr,0,9,1));
  }
  </code></pre>
  <p>But I think this is not right, as player2 also plays smartly. What am I missing?</p>