Cod sursa(job #346009)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 6 septembrie 2009 11:03:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<fstream>
using namespace std;
int a[100001],i,j,n,best[100001],prev[100001],scrmax[100001];
int main()
{ifstream in("scmax.in");
ofstream out("scmax.out");
in>>n;
for(int i=1;i<=n;i++) {in>>a[i];best[i]=1;}

best[1]=1;prev[1]=0;
int max=1,poz=1;
for(int i=2;i<=n;i++) {for(int j=1;j<i;j++) if(a[j]<a[i] && best[i]<best[j]+1) {best[i]=best[j]+1;prev[i]=j;} 
                               if(max<best[i]) {max=best[i]; poz=i;}}
out<<max<<'\n';
for(int i=1;i<=max;i++)
 {scrmax[i]=a[poz];poz=prev[poz];}
for(int i=max;i>0;i--)
{out<<scrmax[i]<<" ";}                               


    
    
    return 0;}