Pagini recente » Cod sursa (job #622340) | Cod sursa (job #2103036) | Cod sursa (job #97852) | Cod sursa (job #773966) | Cod sursa (job #2978306)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int a[100005];
int dp[100005][3];// dp[i][0/1/2]= suma maxima stiind ca am la activ 0/1/2 luate
int main()
{
int n;
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> a[i];
}
// am efect circular, deci pot avea si combinatii de (primul, ultimul)
a[0] = a[n];
a[n + 1] = a[1];
int rez = -1;
// am 3 pos:
//-iau ultimul si primul element(start=0 si termin pe n-1)
//-iau primul element fara ultimul(start=1)
//-nu iau primul element(start=2 si voi termina pe n+1)
//
// OBS:
// la o pozitie, pot ori sa iau sau sa nu iau un element
// si daca il iau, el poate fi primul sau al doilea element luat
//
for (int start = 0; start <= 2; start++) {
dp[start][0] = 0;
dp[start][1] = a[start];
dp[start][2] = 0;
for (int i = start+1; i <= n+start-1; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = dp[i - 1][1] + a[i];
dp[i][1] = dp[i - 1][0] + a[i];
}
rez = max(dp[n + start - 1][0], rez);
}
fout << rez;
return 0;
}