Pagini recente » Cod sursa (job #2534932) | Cod sursa (job #1498762) | Cod sursa (job #2839297) | Cod sursa (job #1510002) | Cod sursa (job #36347)
Cod sursa(job #36347)
/* Time Complexity: O(N) */
#include <stdio.h>
#define filein "oo.in"
#define fileout "oo.out"
#define maxn 100010
#define maxim(a,b) ((a>b)?a:b)
long long eggs[maxn];
long long best[maxn], max;
int main()
{
long long i, j, k, N;
freopen(filein, "r", stdin);
scanf("%lld", &N);
for (i = 0; i < N; i++)
scanf("%lld", &eggs[i]);
max = 0;
if (N == 2)
max = eggs[0] + eggs[1];
else
{
for (k = 0; k < 2; k = (k+1)%N)
{
best[k] = 0;
best[(k+1)%N] = 0;
best[(k+2)%N] = eggs[(k+1)%N] + eggs[(k+2)%N];
for (i = (k+3)%N; i!=k; i = (i+1)%N)
best[i] = maxim(best[(i-1+N)%N], best[(i-3+N)%N] +
eggs[(i-1+N)%N] + eggs[i]);
max = maxim(max, best[(k-1+N)%N]);
}
}
freopen(fileout, "w", stdout);
printf("%lld\n", max);
return 0;
}