Pagini recente » Istoria paginii runda/rar40 | Cod sursa (job #579089) | Cod sursa (job #1658173) | Cod sursa (job #2557469) | Cod sursa (job #2269082)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int a[100005];
int cache[100005][3];
int n;
int solve(int i, int status) {
if (i >= n - status) {
return 0;
}
if (cache[i][status] != 0) {
return cache[i][status];
}
if (i == 1) {
int v1 = solve(i + 2, 2) + a[i] + a[n];
int v2 = solve(i + 3, 1) + a[i] + a[i + 1];
int v3 = solve(i + 1, 0);
return max(v1, max(v2,v3 ));
}
else {
int v1 = solve(i + 3, status) + a[i] + a[i + 1];
int v2 = solve(i + 1, status);
cache[i][status] = max(v1, v2);
return cache[i][status];
}
}
int main() {
freopen("oo.in", "r", stdin);
freopen("oo.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
printf("%d", solve(1, true));
return 0;
}