Pagini recente » Cod sursa (job #2689244) | Cod sursa (job #1130980) | Cod sursa (job #897303) | Cod sursa (job #1064461) | Cod sursa (job #2570697)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int oua[100005];
int DP0[100005], DP1[100005], DP2[100005];
const int inf = 1000000004;
int main()
{
int n,i,sol = 0;
fin>>n;
for(i = 1; i <= n; i++){
fin>>oua[i];
}
if(n == 2){
fout<<oua[1] + oua[2];
return 0;
}
/**daca il iau pe 1*/ // => ca pe n voi lua doar DP0
DP0[1] = -inf; //imposibil sa le iau si sa nu le iau in acelasi timp
DP1[1] = oua[1]; //suma oualor pana la 1 e cat am luat din 1
DP2[1] = -inf; // imposibil sa fie si luate prin lacomie si sa fie si luate normal
for(i = 2; i <= n; i++){
DP0[i] = max(DP0[i-1],DP2[i-1]);
DP1[i] = DP0[i-1] + oua[i];
DP2[i] = DP1[i-1] + oua[i];
}
sol = max(sol,DP0[n]);
/**daca il iau lacom pe 1*/ // => am luat normal pe n => iau doar DP1[n]
DP0[1] = -inf; // imposibil sa le si iau si sa le las in pace
DP1[1] = -inf; // imposibil sa le iau lacom daca le iau normal
DP2[1] = oua[1]; // posibil si iau lacom doar ce ma pe 1
for(i = 2; i <= n; i++){
DP0[i] = max(DP0[i-1],DP2[i-1]);
DP1[i] = DP0[i-1] + oua[i];
DP2[i] = DP1[i-1] + oua[i];
}
sol = max(sol,DP1[n]);
/**daca nu iau din 1 nimic*/ // => pot lua fie DP2[n], fie DP0[n];
DP0[1] = 0;
DP1[1] = -inf;
DP2[1] = -inf;
for(i = 2; i <= n; i++){
DP0[i] = max(DP0[i-1],DP2[i-1]);
DP1[i] = DP0[i-1] + oua[i];
DP2[i] = DP1[i-1] + oua[i];
}
sol = max(sol,max(DP0[n],DP2[n]));
fout<<sol;
return 0;
}