Cod sursa(job #894659)

Utilizator boby301Bogdan Bacila boby301 Data 26 februarie 2013 22:42:59
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

int v[100005],aux[100005],a[1000005],n,cnt,i,j,lung=0,k,poz;

int main()
{
    f>>n;
    for (i=1;i<=n;i++) {f>>v[i];}
    aux[1]=1;aux[n+1]=2100000000;
    for(i=2;i<=n;i++)
    {
        cnt=0;
        for (j=1;j<=i-1;j++)
        {
            if (v[i]>v[j]&&aux[j]>cnt) {cnt=aux[j];}

        }
        aux[i]=cnt+1;
        if (aux[i]>=lung)
        {
            lung=aux[i];
            poz=i;
        }
    }
    g<<lung;

    k=1;
    a[k]=v[poz];
    for (i=poz-1;i>=1;i--)
    {
        if(aux[i]==aux[poz]-1)
        {
            poz=i;
            k++;
            a[k]=v[i];
        }
    }

    for (i=k;i>=1;i--)
    {
        g<<a[i]<<" ";
    }
}