Pagini recente » Cod sursa (job #1900815) | Cod sursa (job #709029) | Cod sursa (job #1282375) | Cod sursa (job #1375217) | Cod sursa (job #2152256)
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int n,v[Nmax],dp[Nmax][2],sol;
void Citire()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[(i+3)];
fin.close();
v[n+1]=v[1];
v[n+2]=v[2];
v[n+3]=v[3];
}
inline void Reset()
{
int i;
for(i=1;i<=(n+4);i++)
dp[i][1]=dp[i][0]=0;
}
void Rezolvare()
{
int i;
///poz1
dp[2][1]=v[1]+v[2];
for(i=3;i<=n;i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
}
sol=max(dp[n][1],dp[n][0]);
Reset();
///poz2
dp[3][1]=v[2]+v[3];
for(i=4;i<=(n+1);i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
}
sol=max(sol,max(dp[n+1][1],dp[n+1][0]));
Reset();
///poz3
dp[4][1]=v[3]+v[4];
for(i=5;i<=(n+2);i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
}
sol=max(sol,max(dp[n+2][1],dp[n+2][0]));
Reset();
fout<<sol<<"\n";
fout.close();
}
int main()
{
Citire();
Rezolvare();
return 0;
}