Cod sursa(job #532219)

Utilizator hiticas_abelhiticasabel hiticas_abel Data 11 februarie 2011 08:40:48
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<iostream>
#include<fstream>
using namespace std;
long a[100000],n,l[100000],poz[100000],i,j,pozmax;

     int main()
     {
         long max;
         ifstream f("scmax.in");
         f>>n;
         for(i=1;i<=n;i++)
         f>>a[i];
         f.close();
         max=-1;pozmax=1;
         l[n]=1;
         poz[n]=-1;
         
         for(i=n-1;i>=1;i--)
         {
            l[i]=1;poz[i]=-1;
            for(j=i+1;j<=n;j++)
            if(a[i]<a[j]&&l[i]<1+l[j])
            {
            l[i]=1+l[j];poz[i]=j;
            if(l[i]>max)
            max=l[i];
            pozmax=i;
            }
         }
    ofstream g("scmax.out");
    g<<max<<"\n";
    for(i=pozmax;i!=-1;i=poz[i])
    g<<a[i]<<" ";
    g.close();
    return 0;
}