Cod sursa(job #2316593)

Utilizator DianaIfrosaIfrosa Diana DianaIfrosa Data 11 ianuarie 2019 23:15:27
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,a[100005],pozmax,lgmax;
int lg[100005], prec[100005];
void Read()
{
   fin>>n;;
   for(int i=1;i<=n;i++)
   fin>>a[i];
}
void Do()
{  lg[1]=1; prec[1]=0; //primul din sir
for(int i=2;i<=n;i++)
{
    lg[i]=1;  prec[i]=0;
    for(int j=1;j<i;j++)
    if(a[j]<a[i] && lg[j]+1>lg[i])
        {
            lg[i]=lg[j]+1;
            prec[i]=j;
            if(lg[i]>lgmax) {lgmax=lg[i]; pozmax=i;}
        }
}
}
void Write(int x)
{
   if(prec[x]!=0) //merge mai departe
      Write(prec[x]);
   fout<<a[x]<<" "; //ordine

}
void Solve()
{
    Do();
    fout<<lgmax<<"\n";
    Write(pozmax);

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