Pagini recente » Cod sursa (job #1854334) | Cod sursa (job #1357037) | Cod sursa (job #1050841) | Cod sursa (job #2829048) | Cod sursa (job #32851)
Cod sursa(job #32851)
#include <cstdio>
#define FIN "oo.in"
#define FOUT "oo.out"
#define MAX 10001
inline long max (long x, long y) {
return ( x>y ) ? x : y;
}
long N, A[MAX], V[MAX];
// V[x] = maximul pana la pozitia x
inline long elem(long x) {
if ( x<0 ) x+=N;
return (x) % N;
}
long solve() {
if ( N==2 )
return A[0] + A[1];
if ( N==3 )
return max(A[0]+A[1],A[1]+A[2]);
long ret = 0,i;
// unim pe primul cu al doilea.
V[N-1] = 0, V[0] = 0;
V[1] = A[0] + A[1];
for (i=3; i<N-1; ++i)
V[i] = max(V[i-1], V[i-3] + A[i] + A[i-1]); // nu luam pe i sau luam pe i unit cu i-1
if ( ret<V[N-2] )
ret = V[N-2];
//unim pe ultimul cu primul.
V[N-1] = V[N-2] = 0;
V[0] = A[0] + A[N-1];
for (i=2; i<N-2; ++i)
V[i] = max(V[i-1], V[elem(i-3)]+ A[i]+A[i-1]);
if ( ret<V[N-3] )
ret = V[N-3];
//unim pe al doilea cu al treilea...
V[1] = V[0] = 0;
V[2] = A[1] + A[2];
for (i=3; (i<N && i>=3); i=elem(i+1))
V[i] = max(V[elem(i-1)], V[elem(i-3)] + A[i] + A[elem(i-1)]);
if ( ret<V[N-1] )
ret = V[N-1];
return ret;
}
int main() {
long i;
freopen(FIN, "r", stdin);
scanf("%ld", &N);
for (i=0; i<N; ++i)
scanf("%ld", A+i);
fclose(stdin);
freopen(FOUT, "w", stdout);
printf("%ld\n", solve());
fclose(stdout);
return 0;
}