Cod sursa(job #873541)

Utilizator bogdan353Costea Bogdan bogdan353 Data 7 februarie 2013 12:59:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb

#include<fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

 int N , maximus = 0 , final[ 100001 ] , pozitie;
int a[ 100001 ] , best[ 100001 ] , tata[ 100001 ];

 int main()
{
  f>>N;

  for( int i = 1 ; i <= N ; i++)
  {
      f>>a[i];

      int maxim=0;

      for( int j = 1 ; j < i ; j++)
      {
          if(a[ i ] > a[ j ] && best[ j ] > maxim)
          {
              maxim = best[ j ];
              tata[ i ] = j;

          }

      }

      best[ i ] = maxim + 1;

      if(best[ i ] > maximus)
      {
          maximus = best[ i ];
          pozitie = i;
      }



  }

      g<<maximus<<"\n";

      int dimensiune = 0;

      for( int i = pozitie ; i != tata[ i ] ; i = tata[ i ])
          final[++dimensiune]=a[i];

        for( int i = dimensiune ; i >= 1 ; i--)
        g<<final[i]<<" ";




}