gistfile1.cpp

#include<cstdio>
#include<vector>
#include<iostream>
#define INF 2000000000
using namespace std;

int Z, n;
int A[2004];
int max_P;

int P[2004][2004];
int D[2004][2004];

void load_data();
void cleaning();
void calculate();
int calculate_minimal_cost(int, int);
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    load_data();
    cleaning();
    calculate();
    print_data();
  }
  return 0;
}

void load_data() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int tmp1;
    scanf("%d", &tmp1);
    A[i] = A[i+n] = tmp1;
  }
}

void cleaning() {
  max_P = -1;
  for (int i = 0; i < 2*(n+1); i++) {
    P[i][i] = A[i];
    D[i][i] = 0;
  }
}

void calculate() {
  for (int j = 1; j < n; j++) {
    for (int i = 0; i < n; i++) {
      calculate_minimal_cost(i, i+j);
    }
  } 
}

int calculate_minimal_cost(int i, int j) {
  P[i][j] = max(A[i] + D[i+1][j], A[j] + D[i][j-1]);
  D[i][j] = min(P[i+1][j], P[i][j-1]);

  if (j-i == n-1) {
    max_P = max(max_P, P[i][j]);
  }
} 

void print_data() {
  printf("%d\n", max_P);
}