Pagini recente » Cod sursa (job #186948) | Cod sursa (job #1006449) | Cod sursa (job #1070945) | Cod sursa (job #2018913) | Cod sursa (job #2241491)
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 2000000005;
const int NMAX = 100005;
int dp[NMAX];
int v[NMAX];
int n;
int main()
{
freopen("oo.in","r",stdin);
freopen("oo.out","w",stdout);
scanf("%d",&n);
int ma = -INF;
for(int i = 1 ; i <= n ; i++)
scanf("%d",&v[i]);
/// cazul 1 - luam 1 si 2
dp[1] = v[1];
dp[2] = v[1]+v[2];
for(int i = 3 ; i < n ; i++)
dp[i] = max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
ma = max(ma,dp[n-1]);
/// cazul 2 - luma n si 1
dp[1] = v[n]+v[1];
dp[2] = v[n]+v[1];
for(int i = 2 ; i < n-1 ; i++)
dp[i] = max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
ma = max(ma,dp[n-2]);
///cazul 3 - nu o luam pe prima
dp[1] = 0;
dp[2] = v[2];
dp[3] = v[2]+v[3];
for(int i = 4; i <= n ; i++)
dp[i] = max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
ma = max(ma,dp[n]);
printf("%d",ma);
return 0;
}