Pagini recente » Cod sursa (job #3334460) | Cod sursa (job #2998872) | Cod sursa (job #3352208) | Cod sursa (job #920984) | Cod sursa (job #3340284)
#include <bits/stdc++.h>
using namespace std;
// DP liniar pe intervalul [start, end] (inclusiv)
long long dp_linear(const vector<int>& a, int start, int end) {
int N = a.size();
int len = end - start + 1;
if (len <= 0) return 0;
if (len == 1) return 1LL * a[start] + a[(start + 1) % N];
if (len == 2)
return max(1LL * a[start] + a[(start + 1) % N],
1LL * a[start + 1] + a[(start + 2) % N]);
// Inițializare
long long dp0 = 0; // dp[i-3]
long long dp1 = 1LL * a[start] + a[(start + 1) % N]; // dp[i-2]
long long dp2 = max(dp1, 1LL * a[start + 1] + a[(start + 2) % N]); // dp[i-1]
long long dp_curr;
for (int i = start + 2; 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(const vector<int>& a) {
int N = a.size();
if (N == 2) return 1LL * a[0] + a[1];
// Caz 1: ignorăm ultima pereche (N-1,0)
long long case1 = dp_linear(a, 0, N - 2);
// Caz 2: ignorăm prima pereche (0,1)
long long case2 = dp_linear(a, 1, N - 1);
return max(case1, case2);
}
int main() {
freopen("oo.in", "r", stdin);
freopen("oo.out", "w", stdout);
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++) cin >> a[i];
cout << max_oua(a) << "\n";
return 0;
}