Pagini recente » Cod sursa (job #793976) | Cod sursa (job #1907942) | Istoria paginii utilizator/karina_antoniu | Cod sursa (job #1708078) | Cod sursa (job #2489716)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("oo.in");
ofstream cout("oo.out");
int dp[100003],a[100003],n;
/// dp[i] = suma maxima obtinuta din primele i numere
/// dp[i] =max(dp[i-1],dp[i-2], 0);
int main()
{
int i,M;
cin>>n;
for(i=1; i<=n; i++)
{
cin>>a[i];
}
/// aleg obligatoriu pe a[1]+a[2]
dp[1]=0;
dp[2]=a[1]+a[2];
dp[3]=dp[2];
dp[4]=dp[3];
for(i=5; i<n; i++)
{
dp[i]=max(dp[i-1],a[i]+a[i-1]+dp[i-3]);
}
M=dp[n-1];
/// aleg obligatoriu pe a[2]+a[3]
dp[1]=0;
dp[2]=0;
dp[3]=a[2]+a[3];
dp[4]=dp[5]=dp[3];
for(i=6; i<=n; i++)
dp[i]=max(dp[i-1],a[i]+a[i-1]+dp[i-3]);
M=max(M,dp[n]);
/// aleg obligatoriu pe a[1]+a[n]
dp[1]=a[1]+a[n];
dp[2]=dp[3]=dp[1];
for(i=4; i<=n-2; i++)
dp[i]=max(dp[i-1],a[i]+a[i-1]+dp[i-3]);
M=max(M,dp[n-2]);
cout<<M;
return 0;
}