Cod sursa(job #1455325)

Utilizator Cudrici_CarinaCudrici Carina Cudrici_Carina Data 27 iunie 2015 16:11:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
using namespace std;
ifstream fi("scmax.in");
ofstream fo("scmax.out");
long long a[100001],b[100001],n,maxi,i,j,s,poz,ult,c[100001],m;
int main()
{ fi>>n;
for (i=1;i<=n;i++)
fi>>a[i];

for (i=1;i<=n;i++)
   { maxi=0;
    for (j=0;j<i;j++)
    if (a[i]>a[j]) maxi=max(maxi,b[j]);
    b[i]=maxi+1;
   }

// for (i=1;i<=n;i++)
//fo<<b[i]<<' ';fo<<endl;

 for (i=1;i<=n;i++)
 s=max(s,b[i]);

 fo<<s<<endl;

 for (i=1;i<=n;i++)
 if (b[i]==s) poz=i;


 c[++m]=a[poz];
 s--;
 ult=a[poz];
 while (s)
 {
     maxi=0;
     for (i=n;i>=1;i--)
     if (b[i]==s  and a[i]<ult ) maxi=max(maxi,a[i]);
     c[++m]=maxi;
     ult=maxi;
     s--;
 }
for (i=m;i>=1;i--)
 fo<<c[i]<<' ';

     return 0;
}