Pagini recente » Cod sursa (job #1090950) | Cod sursa (job #1259175) | Cod sursa (job #815854) | Cod sursa (job #1541129) | Cod sursa (job #2489715)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
/// a = 3 4 0 1 0 6 7 1 2 1
/// dp= 0 7 7 7 8 13 20 20 20
int N, DP[100001] , A[100001];
int main()
{
int i , X , M;
fin >> N;
for(i = 1 ; i <= N ; ++i)
fin >> 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]);
fout << M;
return 0;
}