Cod sursa(job #2044866)

Utilizator grecubogdanGrecu Bogdan grecubogdan Data 21 octombrie 2017 15:28:41
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100001],l[100001],t[100001],n,i,maxx,nrm,j;
int main()
{
 f>>n;
 for(i=1;i<=n;i++)
    f>>a[i];
 t[n]=0;
 l[n]=1;
 maxx=0;
 nrm=0;
 for(i=n-1;i>=1;i--)
 {
     for(j=i+1;j<=n;j++)
     {
         if(a[i]<a[j]&&l[j]+1>l[i])
         {
             l[i]=l[j]+1;
             t[i]=j;
         }
     }
     if(maxx<l[i])
        {
            maxx=l[i];
            nrm=i;
        }
 }
 g<<maxx<<'\n';
 i=nrm;
 g<<a[i]<<" ";
 while(t[i]!=0)
 {
     i=t[i];
    g<<a[i]<<" ";
 }

 return 0;
}