Pagini recente » Cod sursa (job #2635637) | Cod sursa (job #2053323) | Cod sursa (job #1634670) | Cod sursa (job #2098222) | Cod sursa (job #3261774)
#include <bits/stdc++.h>
using namespace std;
/**
10
a = 3 4 0 1 0 6 7 1 2 1
b = 0 7 7 7 8 13 20 20 20 0
c = 4 4 4 5 5 10
d = 4 4 4
b[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[1]+a[2]
c[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[1]+a[n]
d[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[n-1]+a[n]
e[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[2]+a[3]
*/
ifstream fin("oo.in");
ofstream fout("oo.out");
int a[100002], b[100002], c[100002], d[100002], e[100002], n;
int main()
{
int i, mx;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i];
/// b:
b[1] = 0;
b[3] = b[4] = b[2] = a[1] + a[2];
for (i = 5; i < n; i++)
{
b[i] = b[i - 1];
if (b[i] < a[i] + a[i - 1] + b[i - 3])
b[i] = a[i] + a[i - 1] + b[i - 3];
}
/// c:
c[1] = c[2] = c[3] = a[1] + a[n];
for (i = 4; i <= n - 2; i++)
{
c[i] = c[i - 1];
if (c[i] < a[i] + a[i - 1] + c[i - 3])
c[i] = a[i] + a[i - 1] + c[i - 3];
}
/// d:
d[n] = d[1] = d[2] = a[n] + a[n - 1];
for (i = 3; i <= n - 3; i++)
{
d[i] = d[i - 1];
if (d[i] < a[i] + a[i - 1] + d[i - 3])
d[i] = a[i] + a[i - 1] + d[i - 3];
}
/// d:
e[1] = e[2] = 0;
e[3] = e[4] = a[2] + a[3];
for (i = 5; i <= n; i++)
{
e[i] = e[i - 1];
if (e[i] < a[i] + a[i - 1] + e[i - 3])
e[i] = a[i] + a[i - 1] + e[i - 3];
}
/// sol: max(b[n-1], c[n-2], d[n-3], e[n])
mx = max({b[n - 1], c[n-2], e[n]});
fout << mx << "\n";
return 0;
}