Pagini recente » Cod sursa (job #2863084) | Cod sursa (job #288223) | Cod sursa (job #3030654) | Cod sursa (job #1687351) | Cod sursa (job #2978301)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int a[100005];
int main()
{
int n;
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> a[i];
}
int dp[100005][3];// dp[i][0/1/2]= suma maxima stiind ca am la activ 0/1/2 luate
a[0] = a[n];
a[n + 1] = a[1];
//iau primul element
dp[1][0] = 0;
dp[1][1] = a[1];
dp[1][2] = 0;
for(int i = 2; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = dp[i - 1][1] + a[i];
dp[i][1] = dp[i - 1][0] + a[i];
}
int rez = -1;
rez = max(rez, dp[n][0]);
// iau si primul si ultimul element
int dp2[100005][3];
dp2[0][0] = 0;
dp2[0][1] = a[0];
dp2[0][2] = 0;
for (int i = 1; i <= n - 1; i++) {
dp2[i][0] = max(dp2[i - 1][0], dp2[i - 1][2]);
dp2[i][2] = dp2[i - 1][1] + a[i];
dp2[i][1] = dp2[i - 1][0] + a[i];
}
// cout << dp2[1][2];
rez = max(rez, dp2[n - 1][0]);
// nu iau primul elemenr
int dp1[100005][3];
dp1[2][0] = 0;
dp1[2][1] = a[2];
dp1[2][2] = 0;
for (int i = 3; i <= n + 1; i++) {
dp1[i][0] = max(dp1[i - 1][0], dp1[i - 1][2]);
dp1[i][2] = dp1[i - 1][1] + a[i];
dp1[i][1] = dp1[i - 1][0] + a[i];
}
rez = max(rez, dp1[n + 1][0]);
fout << rez;
// cout << dp[n][0];
return 0;
}