Cod sursa(job #262341)

Utilizator redkar23Dezactiveazama redkar23 Data 19 februarie 2009 11:32:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>

using namespace std;

fstream f;
fstream g;
int vect[100000];
int ct[100000];
int i,j;
int n;

int main()
{
    f.open("scmax.in",fstream::in);
    f >> n;
    for(i=0;i<n;i++)
       f >> vect[i];
    f.close();
    
    g.open("scmax.out",fstream::out);
     int max[2];
     max[0]=1;
      
    ct[n-1]=1;
    for(i=n-2;i>=0;i--)
    {
          ct[i]=1;
          for(j=i+1;j<n;j++)
            if(vect[i]<vect[j])
               if(ct[i]<=ct[j])
               {
                  ct[i]=ct[j]+1;
                  if(ct[i]>max[0])
                    {
                       max[0]=ct[i];
                       max[1]=i;              
                    }   
               }
    }
    

     g << max[0] << "\n";
     for(i=max[1];i<n;i++)
        if(max[0] == ct[i])
        {
              g << vect[i] << " ";
              max[0]--;
        }   
     g.close();
    
    return 0;
}