#include #define MAXN 10000 int N, s[MAXN]; int Z1[2][MAXN]; int Z2[2][MAXN]; // Z1[0][i] označuje největší možný zisk na úseku délky l-1 začínajícím dílkem i // pro hráče, který na tomto úseku začíná // Z1[1][i] totéž pro délku l, Z2 analogicky pro nezačínajícího hráče int max(int a, int b) { return a > b ? a : b; } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &s[i]); Z1[0][i] = s[i]; } int d = 0; // d označuje index pro Z1 odpovídající l-1 for (int l = 2; l <= N; l++) { for (int i = 0; i < N; i++) { int ip = i + 1; if (ip == N) ip = 0; int j = i + l - 1; j %= N; //A a B jsou 2 možné tahy int ziskA = s[i] + Z2[d][ip]; int ziskB = s[j] + Z2[d][i]; if (ziskA > ziskB) { Z1[1-d][i] = ziskA; Z2[1-d][i] = Z1[d][ip]; } else { Z1[1-d][i] = ziskB; Z2[1-d][i] = Z1[d][i]; } } d = 1 - d; } int vysledek = 0; for (int i = 0; i < N; i++) { vysledek = max(Z1[d][i], vysledek); } printf("%d\n", vysledek); return 0; }