Mai intai trebuie sa te autentifici.
Cod sursa(job #1199605)
| Utilizator | Data | 19 iunie 2014 21:22:46 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 20 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.27 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
long n,i,j,A[100013],P[100013],coef,Pbest,pivot,sol(0),Ssol[100013];
int main()
{
cin>>n;
for (i=1;i<=n;++i) {
cin>>A[i];
P[i]=A[i];
}
for (i=2;i<=n;++i){
coef=0;
Pbest=0;
for (j=i-1; j>0;--j)
if (A[j]<A[i]) Pbest=max(Pbest,P[j]);
P[i]=P[i]+Pbest;
}
for (i=1;i<=n;++i) {
Pbest=max(Pbest,P[i]);
if (P[i]==Pbest) pivot=i;
}
while (Pbest!=0) {
Pbest-=A[pivot];
Ssol[++sol]=A[pivot];
for (i=pivot-1;i>=1;--i) if (P[i]==Pbest) {
pivot=i;
break;
}
}
cout<<sol<<"\n";
for (i=sol;i>=1;--i) cout<<Ssol[i]<<" ";
return 0;
}
