Pagini recente » Cod sursa (job #1223075) | Cod sursa (job #2494776) | Cod sursa (job #2134353) | Cod sursa (job #3140244) | Cod sursa (job #2152259)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
const int nMax = 100001;
int n;
int a[nMax], dp[nMax];
void Read() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i];
fin.close();
}
void Solve() {
int i;
/// Cazul 1. Iau primele 2 gaian
dp[1] = a[1];
dp[2] = a[1] + a[2];
for (i = 3; i < n; i++)
dp[i] = max(a[i - 1] + a[i] + dp[i - 3], dp[i - 1]);
int ans = dp[n - 1];
/// Cazul 2. Nu iau prima gaina
dp[1] = 0;
dp[2] = a[2];
dp[3] = a[2] + a[3];
for (i = 4; i <= n; i++) {
dp[i] = max(a[i - 1] + a[i] + dp[i - 3], dp[i - 1]);
}
ans = max(ans, dp[n]);
/// Cazul 3. nu iau primele2 gaini
dp[1] = 0;
dp[2] = 0;
dp[3] = a[3];
dp[4] = a[3] + a[4];
for (i = 5; i <= n; i++) {
dp[i] = max(a[i - 1] + a[i] + dp[i - 3], dp[i - 1]);
}
ans = max(ans, dp[n]);
fout << ans << "\n";
}
int main() {
Read();
Solve();
return 0;
}