Cod sursa(job #820856)

Utilizator kiralalaChitoraga Dumitru kiralala Data 21 noiembrie 2012 11:52:00
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream o("scmax.out");
int n,x[100001],len[100001],pred[100001],maxim,poz;

void search(int a)
{
    len[a]=1; pred[a]=0;
    for(int i=a;i<=n;i++)
    {
        if(x[a]<x[i])
        {
            len[a]=len[i]+1;
            pred[a]=i;
            if(len[a]>maxim)
                maxim=len[a],poz=a;
        break;
        }
    }
}

int main()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x[i];
    }

    for(i=n;i>0;i--)
    {
        search(i);
    }

    o<<maxim<<'\n';

    for(i=1;i<=maxim;i++)
    {
        o<<x[poz]<<' ';
        poz=pred[poz];
    }

    return 0;
}