 <p>As the OP mentioned that both player play the game optimally,I am going to present an algorithm under this assumption.</p> <p><strong>Definitely if both players play optimally,then definitely the sum they obtain at the end would be maximum,otherwise they are not playing optimally.</strong></p> <p>There are two different cases here:</p> <p><strong>I make the first move and pick element at position x</strong></p> <p>Now because we have to obey the condition that only adjacent elements could be picked,let me define two arrays here.</p> <p>left[x]: It is the sum of elements that can be obtained by adding </p> <pre><code>array[0],array[1]....array[x-1],the elements left to x. </code></pre> <p>right[x]: It is the sum of elements that can be obtained by adding </p> <pre><code>array[x+1],array[x+2]....array[n-1],the elements right to x. </code></pre> <p>Now,because the other player also plays optimally,what he will do is he will check what I can possibly achieve and he finds that,I could achieve the following:</p> <pre><code>array[x] + left[x] = S1 </code></pre> <p><strong>OR</strong></p> <pre><code>array[x] + right[x] = S2 </code></pre> <p>So what the other player does is finds the minimum of the S1 and S2.</p> <p><strong>If S1 &lt; S2 this means that if the other player picks element at x+1,he just took away the better part of array from us because now we are left with a lesser sum S1</strong></p> <p><strong>If S1 > S2 this means that if the other player picks element at x-1,he just took away the better part of array from us because now we are left with a lesser sum S2</strong></p> <p><strong>Because I am also playing optimally I would in the very first move pick such x which has minimum absolute value of (right[x]-left[x]),so that even if our opponent takes the better part of array from us,he is only able to take away minimum</strong></p> <p>Therefore,If both players play optimally, the maximum sums obtained are:</p> <p><strong>Update.</strong></p> <pre><code>x + left[x] and right[x]//when second player in his first move picks x+1 </code></pre> <p>Therefore,in this case the moves made are:</p> <pre><code>Player 1:Picks element at position x,x-1,x-2....0. Player 2:Picks element at position x+1,x+2,....n-1 </code></pre> <p>Because each player has to pick adjacent element to the previously picked element by him.</p> <p><strong>OR</strong></p> <pre><code>x + right[x] and left[x]//when second player in his first move picks x-1 </code></pre> <p>Therefore,in this case the moves made are:</p> <pre><code>Player 1:Picks element at position x,x+1,x+2....n-1. Player 2:Picks element at position x-1,x-2,....0. </code></pre> <p>Because each player has to pick adjacent element to the previously picked element by him.</p> <p><strong>where x is such that we obtain minimum absolute value of (right[x]-left[x]).</strong></p> <p>Since OP insisted on posting pseudocode,here is one:</p> <p>Computing the left and right array.</p> <pre><code>for(i = 0 to n-1) { if(i==0) left[i]=0; else left[i] = left[i] + array[i-1]; j = n-1-i; if(j==n-1) right[j]=0; else right[j]= right[j] + array[j+1]; } </code></pre> <p>The left and right arrays initially have 0 in all positions.</p> <p>Computing max_sums.</p> <pre><code>Find_the_max_sums() { min = absoulte_value_of(right[0]-left[0]) x = 0; for(i = 1 to n-1) { if( absolute_value_of(right[i]-left[i]) &lt; min) { min = absolute_value_of(right[i]-left[i]); x=i; } } } </code></pre> <p>Clearly Both space and time complexity of this algorithm is linear.</p>