Cod sursa(job #2261364)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 16 octombrie 2018 10:32:01
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#define DMAX 100005

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[DMAX],lis[DMAX],urm[DMAX],n;
void citire();
void pd();
void afisare();
int main()
{
    citire();
    pd();
    afisare();
    return 0;
}
void citire()
{int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    lis[n]=1;
    urm[n]=0;
}
void pd()
{int i,maxim,j,next;
  for(i=n-1;i>=1;i--)
  {
      maxim=1; next=0;
      for(j=i+1;j<=n;j++)
          if(a[i]<a[j]&&lis[j]+1>maxim)
             {maxim=lis[j]+1;
              next=j;
             }
      lis[i]=maxim;
      urm[i]=next;
  }
}
void afisare()
{int maxi=lis[1],pozmax=1,i;
    for(i=2;i<=n;i++)
        if(lis[i]>maxi)
           {maxi=lis[i];
            pozmax=i;
           }
    fout<<maxi<<'\n';
    fout<<a[pozmax]<<' ';
    while(urm[pozmax])
    {
          pozmax=urm[pozmax];
          fout<<a[pozmax]<<' ';
    }
    fout<<'\n';
}