Pagini recente » Cod sursa (job #3307264) | Cod sursa (job #3350234) | Monitorul de evaluare | Cod sursa (job #3341523) | Cod sursa (job #3341526)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int n;
int v[100005];
int p[100005]; // pair sums
// Run the suma2 DP on p[l..r], return max sum
int solve(int l, int r) {
int len = r - l + 1;
if (len <= 0) return 0;
vector<int> dp(len + 2, 0);
// reindex: dp[1] = p[l], dp[2] = p[l+1], ...
dp[0] = 0;
dp[1] = max(0, p[l]);
for (int i = 2; i <= len; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + p[l + i - 1]);
}
return dp[len];
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i];
// Build pair sums (circular)
for (int i = 1; i <= n; i++)
p[i] = v[i] + v[i % n + 1]; // p[n] = v[n]+v[1]
// Case 1: pairs p[1..n-1] (can't use p[n] since it overlaps with p[1])
int ans1 = solve(1, n - 1);
// Case 2: pairs p[2..n]
int ans2 = solve(2, n);
fout << max(ans1, ans2);
return 0;
}