Pagini recente » Cod sursa (job #1381291) | Cod sursa (job #2452445) | Cod sursa (job #394857) | Rating Suciu Lavinia-Florina (Laviniut) | Cod sursa (job #2241490)
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 2000000005;
const int NMAX = 100005;
int dp[NMAX][3];
int v[NMAX];
int n;
inline void INIT()
{
for(int i = 1 ; i <= n ; i++)
dp[i][0] = dp[i][1] = -INF;
}
int main()
{
freopen("oo.in","r",stdin);
freopen("oo.out","w",stdout);
scanf("%d",&n);
int a,b;
for(int i = 1 ; i <= n ; i++)
scanf("%d",&v[i]);
///cazul 1 in care NU il luam pe 1
INIT();
dp[1][0] = 0;
dp[1][1] = -INF;
for(int i = 2 ; i <= n ; i++)
{
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
if(i == 2)
dp[i][1] = dp[n][0]+v[i]+v[i-1];
else
dp[i][1] = dp[i-2][0]+v[i]+v[i-1];
}
a = max(dp[n][1],dp[n][0]);
///cazul 2 in care il luam pe 1
INIT();
dp[1][0] = -INF;
dp[1][1] = 0;
for(int i = 2 ; i <= n ; i++)
{
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
if(i == 2)
dp[i][1] = dp[n][0]+v[i]+v[i-1];
else
dp[i][1] = dp[i-2][0]+v[i]+v[i-1];
}
b = max(dp[n][1],dp[n][0]);
printf("%d\n",max(a,b));
return 0;
}