Cod sursa(job #1998324)

Utilizator passwordCiaciru Ana Maria password Data 7 iulie 2017 14:36:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#define nmax 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, a[nmax];///date de intrare
int lg[nmax];///lg[i]-lg max a unui subsir terminat in a[i]
int t[nmax];///t[i]-elemem anterior lui a[i] in subsir

void Read()
{int i;
 fin>>n;
 for(i=1;i<=n;i++)
    fin>>a[i];
}

void pd()
{int i,j;
 lg[1]=1; t[1]=0;
 for(i=2;i<=n;i++)
   {lg[i]=1; t[i]=0;
    for(j=1;j<i;j++)
       if(a[j]<a[i]&&lg[j]+1>lg[i])
         {lg[i]=lg[j]+1;
          t[i]=j;}
   }
}


void Write(int x)
{if(t[x]!=0) Write(t[x]);
 fout<<a[x]<<" ";
}

void Solve()
{int i;
 int imax,lgmax=0;
 for(i=1;i<=n;i++)
    if(lg[i]>lgmax)
     {lgmax=lg[i];
      imax=i;}
 fout<<lgmax<<"\n";
 Write(imax);
 fout<<endl;
}

int main()
{Read();
 pd();
 Solve();
 return 0;
}