Cod sursa(job #629157)

Utilizator VladberilaVladutz Vladberila Data 2 noiembrie 2011 18:37:24
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
long s[100001],n,maxx[100001],i,j,poz[100001],maxim=1,start=1,pos,maxj;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
       f>>s[i];
    maxx[1]=1;
    for(i=2;i<=n;i++)
    {
       maxx[i]=1;
       for(j=i-1;j>=1;j--)
       {
           maxj=1;
           if(s[i]>s[j])
           {
               if(maxx[j]>maxj)
               {
                   pos=j;
                   maxj=maxx[j];            
               }
           }
           maxx[i]=1+maxj;
           poz[i]=pos;
           if(maxx[i]>maxim)
           {
                maxim=maxx[i];
                start=i;            
           }
       }
    } 
    g<<maxim<<'\n';
    i=start;
    for(j=1;j<=maxim;j++)
    {
        maxx[j]=s[i];
        i=poz[i];                 
    }
    for(i=maxim;i>=1;i--)
        g<<maxx[i]<<' ';
    f.close();
    g.close();
    return 0;
}