Pagini recente » Cod sursa (job #1949234) | Cod sursa (job #2574073) | Cod sursa (job #802133) | Cod sursa (job #1612802) | Cod sursa (job #1251953)
#include <stdio.h>
#include <string.h>
#define MAXN 100001
#define INF 0x3f3f3f3f
int maxim(int a, int b)
{
return (a > b) ? a : b;
}
int compute_dp(int start, int stop, int *dp, int *v)
{
int i, tmp;
for (i = start; i <= stop; i++) {
dp[i] = maxim(v[i - 1] + v[i] + dp[i - 3], dp[i - 1]);
}
tmp = dp[stop];
memset(dp, 0, sizeof(dp));
return tmp;
}
int main()
{
FILE *fdin = fopen("oo.in", "r");
FILE *fdout = fopen("oo.out", "w");
int v[MAXN], dp[MAXN], n, i, ret, sol;
fscanf(fdin, "%d", &n);
for (i = 1; i <= n; i++)
fscanf(fdin, "%d", &v[i]);
// case1: taking (1, 2)
dp[2] = dp[3] = dp[4] = v[1] + v[2];
sol = dp[2];
ret = compute_dp(5, n - 1, dp, v);
if (ret > sol) sol = ret;
// case2: taking (1, n)
dp[1] = dp[2] = dp[3] = v[1] + v[n];
ret = compute_dp(4, n - 2, dp, v);
if (ret > sol) sol = ret;
// case3: the rest of it
dp[0] = dp[1] = dp[2] = 0;
ret = compute_dp(3, n, dp, v);
if (ret > sol) sol = ret;
fprintf(fdout, "%d\n", sol);
fclose(stdin);
fclose(stdout);
return 0;
}