title: Collect cards of largest total value when kept in a line (extraction only from the corners)
body: <p>Consider the following game.</p>
  
  <p>A dealer produces a sequence s1 ...sn of cards, face up, where
  each card si has a value vi. Then two players take turns picking a card from the sequence, but
  can only pick the rst or the last card of the (remaining) sequence. The goal is to collect cards of
  largest total value. (For example, you can think of the cards as bills of different denominations.)</p>
  
  <p>Give an O(n^2) algorithm to compute an optimal strategy for the first player(Just the maximum obtainable code).</p>
  
  <p>I have tried solving it legthwise and possible solved it here is my code...
  The  array cards has the values of each card.. The 0 th element of the cards is unused and waste(Base indexing 1)!</p>
  
  <pre><code>  #include&lt;bits/stdc++.h&gt;
    using namespace std;
    int main()
    {
     int cards[]={0,2,100,101,1};
     int n=4;
     int i,j,l,sum=204;
     int dp[n+1][n+1];
     memset(dp,0,sizeof(dp));
     for(i=1;i&lt;=n;i++)
        dp[i][i]=cards[i];
     for(l=2;l&lt;=n;l++)
     {
        for(i=1;i&lt;=n-l+1;i++)
                {
                    j=i+l-1;
                    dp[i][j]=max(cards[i]-dp[i+1][j],cards[j]-dp[i][j-1]);
                 }
      }
      printf("%d\n",(sum+dp[1][n])/2);
  
      return 0;
      }
  </code></pre>
  
  <p>In the last print statement I have printed (sum+dp[1][n])/2 just because as the elements are 2n, n will be included and the rest n will be subtracted when I do this operation, I get the sum of included values.</p>
  
  <p>Although, it gives the correct answer, I am still unable to say what does exactly dp[i][j] stands for !! It does not stand for maximum obtainable Value(as it wont give me that value directly).
  So what does it denote is my another question??</p>
  
  <p>Is there any other line of thinking to solve such a problem?</p>