Cod sursa(job #384134)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 19 ianuarie 2010 11:35:54
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
    int n,i,j,poz,v[100005],l[100005],p[100005];
    ifstream fin("scmax.in");
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    l[n]=1;
    p[n]=-1;
    for(i=n-1;i>0;i--)
    {
        poz=0;
        for(j=i+1;j<=n;j++)
            if(v[i]<v[j])
                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=2;i<=n;i++)
        if(l[i]>l[poz])
            poz=i;
    i=poz;
    ofstream fout("scmax.out");
    fout<<l[poz]<<endl;
    while(i!=-1)
    {
        fout<<v[i]<<" ";
        i=p[i];
    }
    fin.close();
    fout.close();
    return 0;
}