Cod sursa(job #1160338)

Utilizator raduraraduIacob Radu raduraradu Data 30 martie 2014 14:26:52
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[100001],l[100001],t[100001],n;
int main()
{
    int i,j,max,poz,max1=-1,poz1;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    t[n]=-1;
    l[n]=1;
    for(i=n-1;i>=1;i--)
    {
        max=0;
        for(j=i;j<=n;j++)
            if(l[j]>max&&a[j]>a[i])
        {
            max=l[j];
            poz=j;
        }
        l[i]=max+1;
        if(l[i]>max1)
        {max1=l[i];
        poz1=i;
        }
        if(l[i]>=2)
        t[a[i]]=a[poz];
        else
        t[a[i]]=-1;
    }
    g<<l[poz1]<<'\n';
    i=a[poz1];
    while(t[i]!=-1)
    {
        g<<i<<" ";
        i=t[i];
    }
    g<<i;
    return 0;
}