Cod sursa(job #765805)

Utilizator kakkarotFaur Catalin kakkarot Data 9 iulie 2012 12:53:49
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cstring>

using namespace std;

int a[100002];
char vect[100002];

int main(void)
{
   int n;
   ifstream cin("scmax.in");
   ofstream cout("scmax.out");
   
   cin >> n;
   int i,j;
   for(i=1;i<=n;i++)
     cin >> a[i];

   vect[n] = 1;
   int max=0;
   int startPos=0;
   
   for(i=n-1;i>=0;i--)
   {
      if(a[i]<a[i+1])
      {
          vect[i]=vect[i+1]+1;
          if(max<vect[i])
             max=vect[i],startPos=i;
          continue;
      }
      if(a[i]==a[i+1])
      {
          vect[i]=vect[i+1];                
      }
      j=i+2;
      while(j<n&&a[i]>a[j])
        j++;
      if(a[i]==a[j])
      {
         vect[i]=vect[j];              
      }        
      if(a[i]>a[j])
         vect[i] = 1;
      if(a[i]<a[j])
        vect[i]=vect[j]+1;
      if(max<vect[i])
         max=vect[i],startPos=i;
   }   
   cout << max << endl;
   for(i=startPos;i<=n;i++)
   {
       if(vect[i]==max)
       {
          cout << a[i] << " ";
          max--;
       }           
                   
   }
   cin.close();
   cout.close();
   return 0;   
}