Pagini recente » Cod sursa (job #2720295) | Cod sursa (job #350656) | Cod sursa (job #2717339) | Cod sursa (job #2933163) | Cod sursa (job #1894413)
#include <bits/stdc++.h>
using namespace std;
ifstream f("Oo.in");
ofstream g("Oo.out");
///3 stari: 0 nu iau din n, 1 iau din i si din precedentul, 2 iau doar din i fara precedentul
const int NMax = 100001;
int n,ans;
int a[NMax];
int dp[NMax][4];
int mx3(int x,int y,int z){
return max(x,max(y,z));
}
int main()
{
f >> n;
for(int i = 1; i <= n; ++i){
f >> a[i];
}
///1 cazul 1: il grupez pe n cu 1
dp[1][0] = 0; dp[1][1] = a[1] + a[n]; dp[1][2] = a[1];
dp[2][0] = dp[1][1]; dp[2][1] = a[1] + a[2]; dp[2][2] = a[2];
for(int i = 3; i < n; ++i){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][2] + a[i];
dp[i][2] = dp[i - 1][0] + a[i];
}
ans = max(ans,dp[n - 1][0]);
///cazul 2: il grupez pe 1 cu 2
memset(dp,0,sizeof(dp));
dp[2][0] = 0; dp[2][1] = a[1] + a[2]; dp[2][2] = a[2];
for(int i = 3; i <= n; ++i){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][2] + a[i];
dp[i][2] = dp[i - 1][0] + a[i];
}
///Aici extrag doar dp[n][0]
ans = max(ans,dp[n][0]);
g << ans << '\n';
return 0;
}