この問題は、 区間DP と呼ばれる動的計画法で解くことができます。
区間DP とは、どの区間に関する情報かを添え字に持つ DP です。
今回の問題の場合、例えば以下の DP テーブルを設計すればよいです。

\(dp[l][r][side] = \) {

• 与えられた数列のうち、区間 \(A_l,A_{l+1},\dots,A_r\) だけに着目して両者とも最適にゲームを行った時の (高橋君の得点) \(-\) (青木君の得点)
• ただし、 \(side=0\) のときは高橋君が初手を打ち、 \(side=1\) のときは青木君が初手を打つ。

}

この DP は再帰の形で回すと考えやすいです。

• \(solve(l,r,side)\) が \(dp[l][r][side]\) を求める関数であるとする。
• \(l>r\) ならこれから始まるのは空の数列に対するゲームなので、 \(0\) を返す。
• \(dp[l][r][side]\) が計算済みなら、その値を返す。
• \(side=0\) なら高橋君の手番であり、高橋君の最適な着手のおかげで以下の \(2\) つの結果のうち 大きい方 を採用することになる。
  • \(solve(l+1,r,1)+A_l\)
  • \(solve(l,r-1,1)+A_r\)
• \(side=1\) なら青木君の手番であり、青木君の最適な着手のおかげで以下の \(2\) つの結果のうち 小さい方 を採用することになる。
  • \(solve(l+1,r,0)-A_l\)
  • \(solve(l,r-1,0)-A_r\)
• 最終的な答えは \(solve(1,N,0)\) である。

これを再帰構造で回すことで、より小さい問題から順に DP テーブルの内容が確定していきます。

\(O(N^2)\) 個の要素がある表があり、ひとつの要素を確定させるのに時間計算量 \(O(1)\) を要するので、全体の時間計算量は \(O(N^2)\) です。

最後に、 \(2\) 人の得点の和 \(s\) は不変 ( \(A\) 全体の和 ) であり、区間 DP で (高橋君の得点) \(-\) (青木君の得点) \(d\) が求まるため、和差算より \(2\) 人の得点が以下のように求まります。

• 高橋君の得点: \((s+d)/2\)
• 青木君の得点: \((s-d)/2\)

メモ: 工夫をすると非再帰で DP を回すことができます。また、少し考えると DP テーブルの大きさを半分にできます ( 実は、 \(side\) の項は不要です。 )

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll big=1e18;

ll N;
ll A[3005];
ll dp[3005][3005][2];

ll solve(ll l,ll r,ll side){
  if(l>r){return 0;}
  if(dp[l][r][side]!=big){
    return dp[l][r][side];
  }

  if(side==0){
    dp[l][r][side]=max(solve(l+1,r,1-side)+A[l],solve(l,r-1,1-side)+A[r]);
  }
  else{
    dp[l][r][side]=min(solve(l+1,r,1-side)-A[l],solve(l,r-1,1-side)-A[r]);
  }
  return dp[l][r][side];
}

int main(){
  ll sum=0;
  cin >> N;
  for(ll i=1;i<=N;i++){
    cin >> A[i];
    sum+=A[i];
  }
  for(ll i=1;i<=N;i++){
    for(ll j=1;j<=N;j++){
      dp[i][j][0]=big;
      dp[i][j][1]=big;
    }
  }

  ll diff=solve(1,N,0);
  cout << (sum+diff)/2 << " ";
  cout << (sum-diff)/2 << "\n";
  return 0;
}