Cod sursa(job #2133575)

Utilizator Monstergentleman35Ciopraga Razvan Monstergentleman35 Data 17 februarie 2018 10:17:24
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int urm[100000],lgmax[100000],V[100000];
int i,j,n,max1,incepmax;

int main()
{
 fin>>n;
 for (i=1;i<=n;i++)
  fin>>V[i];
 V[n+1]=9999999;
 urm[n]=-1;
 for (i=n;i>0;i--)
 {
  for (j=i+1;j<=n+1;j++)
  {
   if (V[j]>V[i]&&lgmax[j]+1>lgmax[i])
   {
    lgmax[i]=lgmax[j]+1;
    if (j<=n)
     urm[i]=j;
    else
     urm[i]=-1;
   }
  }
 }
 for (i=1;i<=n;i++)
  if (max1<lgmax[i])
  {
   max1=lgmax[i];
   incepmax=i;
  }
 fout<<max1<<"\n";
 while (incepmax!=-1)
 {
  fout<<V[incepmax]<<" ";
  incepmax=urm[incepmax];
 }
 fout<<"\n";
 return 0;
}