Pagini recente » Borderou de evaluare (job #1569162) | Cod sursa (job #728242) | Cod sursa (job #1002423) | Cod sursa (job #701240) | Cod sursa (job #3245662)
#include <bits/stdc++.h>
#define VMAX 50000
#define NMAX 100005
#define LOG 19
#define INF (long long)(1e18)
#define MOD 1000000009
#define ll long long int
#define ADD 1e9
#define NIL 0
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int dp[NMAX+1][2];
int n;
int a[NMAX+1];
int main()
{
fin >> n;
for(int i=1;i<=n;i++)
{
fin >> a[i];
}
if(n==2)
{
fout << a[1]+a[2];
return 0;
}
dp[2][1]=a[1]+a[2];
dp[3][0]=dp[2][1];
for(int i=4;i<=n-1;i++)
{
dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
dp[i][1]=a[i]+a[i-1]+dp[i-2][0];
}
int res = max(dp[n-1][1],dp[n-1][0]);
memset(dp,0,sizeof(dp));
dp[3][1]=a[3]+a[2];
dp[4][0]=dp[3][1];
for(int i=5;i<=n;i++)
{
dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
dp[i][1]=a[i]+a[i-1]+dp[i-2][0];
}
res=max(res,max(dp[n][1],dp[n][0]));
memset(dp,0,sizeof(dp));
dp[1][1] = a[1]+a[n];
dp[2][0] = dp[1][1];
for(int i=3;i<=n-2;i++)
{
dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
dp[i][1]=a[i]+a[i-1]+dp[i-2][0];
}
res=max(res,max(dp[n-2][1],dp[n-2][0]));
fout << res;
/// 7 2 3 4 5
}