Cod sursa(job #384467)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 20 ianuarie 2010 09:45:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
using namespace std;
int v[100005],n,l[100005],p[100005];
int main()
{
 int i,j;
 ifstream fin("scmax.in");
 fin>>n;
 for(i=1;i<=n;i++)
  fin>>v[i];
  l[n]=1;
  p[n]=-1;
  int poz;
  for(i=n-1;i>0;i--)
    {
        poz=0;
        for(j=i+1;j<=n;j++)
        if(v[j]>v[i])
           if(poz==0)
              poz=j,p[i]=poz;
           else if(l[j]>=l[poz])
                  poz=j,p[i]=poz;
        if(poz==0)
          l[i]=1,p[i]=-1;
        else l[i]=l[poz]+1;                      
    }
 poz=1;
 for(i=1;i<=n-l[poz]+1;i++)
  if(l[i]>l[poz])
    poz=i;
       
 ofstream fout("scmax.out") ;
 fout<<l[poz]<<endl;
 i=poz;
 while(i!=-1)
  {
   fout<<v[i]<<" ";
   i=p[i];   
  }    
  return 0;
}