Pagini recente » Cod sursa (job #3340281) | Cod sursa (job #3329309) | Cod sursa (job #3327673) | Cod sursa (job #3324894) | Cod sursa (job #3340290)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int a[MAXN];
// DP pe interval de perechi [start..end]
long long dp_linear(int start, int end, int N) {
long long dp0 = 0; // maxim pana la i-3
long long dp1 = 0; // maxim pana la i-2
long long dp2 = 0; // maxim pana la i-1
long long dp_curr;
for (int i = start; i <= end; i++) {
long long pair_sum = 1LL * a[i % N] + a[(i + 1) % N];
dp_curr = max(dp2, dp0 + pair_sum);
dp0 = dp1;
dp1 = dp2;
dp2 = dp_curr;
}
return dp2;
}
long long max_oua(int N) {
if (N == 2) return 1LL * a[0] + a[1];
// Caz 1: ignoram ultima pereche (N-1,0)
long long case1 = dp_linear(0, N - 2, N);
// Caz 2: ignoram prima pereche (0,1)
long long case2 = dp_linear(1, N - 1, N);
return max(case1, case2);
}
int main() {
freopen("oo.in", "r", stdin);
freopen("oo.out", "w", stdout);
int N;
cin >> N;
for (int i = 0; i < N; i++) cin >> a[i];
cout << max_oua(N) << "\n";
return 0;
}