Pagini recente » Cod sursa (job #2967423) | Cod sursa (job #1975646) | Cod sursa (job #182903) | Cod sursa (job #1969877) | Cod sursa (job #2239137)
#include <fstream>
#include <algorithm>
using namespace std;
int dp1[100005][5],dp2[100005][5],dp3[100005][5],v[100005];
int main()
{ ifstream cin("oo.in");
ofstream cout("oo.out");
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
for(int i=1;i<=n-2;i++)
{
if(i!=1&&i!=2)
{
dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]);
dp1[i][1]=v[i]+v[i-1]+dp1[i-2][0];
}
else
{
if(i==1)
{
dp1[i][0]=0;
dp1[i][1]=v[i];
}
else
{
dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]);
dp1[i][1]=v[i]+v[i-1];
}
}
}
for(int i=2;i<=n;i++)
{ if(i!=2){
dp2[i][0]=max(dp2[i-1][0],dp2[i-1][1]);
dp2[i][1]=v[i]+v[i-1]+dp2[i-2][0];}
else
{
dp2[i][0]=0;
dp2[i][1]=v[i];
}
}
dp3[n][0]=0;
dp3[n][1]=v[n];
dp3[1][0]=v[n];
dp3[1][1]=v[1]+v[n];
for(int i=2;i<=n-2;i++)
{
dp3[i][0]=max(dp3[i-1][0],dp3[i-1][1]);
dp3[i][1]=v[i]+v[i-1]+dp3[i-2][0];
}
cout<<max(dp2[n][1],max(dp2[n][0],max(dp1[n-2][1],max(dp1[n-2][0],max(dp3[n-2][0],dp3[n-2][1])))));
return 0;
}