gistfile1.cpp

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

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

int P[1002][1002];
int D[1002][1002];

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] = tmp1;
  }
}

void cleaning() {
  max_P = -1;
  for (int i = 0; i < 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++) {
      if (i == (i+j)%n) continue;
      calculate_minimal_cost(i, (i+j)%n);
    }
  } 
}

int calculate_minimal_cost(int i, int j) {
  //printf("Licze [%d, %d]:\n", i, j); 
  int result;
  //cout << "P: " << A[i] + D[i+1][j] << " albo " << A[j] + D[i][j-1] << endl;
  if((P[i][j] = max(A[i] + D[(i+1)%n][j], A[j] + D[i][(j-1)%n])) > max_P) max_P = P[i][j];
  D[i][j] = min(P[(i+1)%n][j], P[i][(j-1)%n]);
  //printf("%d %d\n", P[i][j], D[i][j]);
} 

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