Cod sursa(job #313799)

Utilizator giuliastefGiulia Stef giuliastef Data 9 mai 2009 18:44:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
// subsir crescator maxim

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    long int a[100000],n,i,j,maxim,lung[100000],poz,lungime;
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    f>>n;
    for(i=1;i<=n;i++)
     f>>a[i];
    lung[n]=1, lungime=1, poz=n;
    for(i=n-1;i>=1;i--)
    {
     maxim=0;
     for(j=i+1;j<=n;j++)
      if(a[i]<a[j])
       if(lung[j]>maxim)
        maxim=lung[j];
     lung[i]=maxim+1;
     if(lung[i]>lungime) lungime=lung[i], poz=i;
    }
    g<<lungime<<"\n";
    g<<a[poz]<<" ";
    for(i=poz+1;i<=n;i++)
     if(lung[i]==lungime-1 && a[poz]<a[i])
     {
      g<<a[i]<<" ";
      lungime=lungime-1;
      poz=i;
     }
    g<<"\n";
    f.close();
    g.close();
    return 0;
}