Cod sursa(job #1808205)

Utilizator petrica_norbyPetrica Norbert Mark petrica_norby Data 17 noiembrie 2016 14:49:49
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
using namespace std;
ifstream fi("scmax.in");
ofstream fo("scmax.out");

int n,i,j,k,a[100005],b[100005],d[100005];
int c[100005],poz,maxi;
int main()
{
    fi>>n;
    for(i=1;i<=n;i++){
       fi>>a[i];
    }
    b[1]=1;
    for(i=2;i<=n;i++){
        maxi=0;
        for(j=1;j<=i-1;j++){
          if(a[j]<a[i])
            if(b[j]>maxi){maxi=b[j];poz=j;}
        }
        b[i]=1+maxi;
        if(maxi)c[i]=poz;
    }
    maxi=0;
    for(i=1;i<=n;i++){
       if(b[i]>maxi){maxi=b[i];poz=i;}
    }
    fo<<maxi<<'\n';
    do{
      d[++k]=a[poz];
      poz=c[poz];
    }while(poz!=0);
    for(i=k;i>=1;i--) fo<<d[i]<<' ';


    return 0;
}