Cod sursa(job #1795447)

Utilizator tanasaradutanasaradu tanasaradu Data 2 noiembrie 2016 14:37:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100005],lis[100005],n;
void Subsir()
{
    int i,maxim,j,aux;
    lis[n]=1;
    for(i=n-1;i>=1;i--)
    {
        maxim=0;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j] and maxim<lis[j])
            maxim=lis[j];
        lis[i]=maxim+1;
    }
    maxim=0;
    for(i=1;i<=n;i++)
        maxim=max(maxim,lis[i]);
    fout<<maxim<<"\n";
    for(i=1;i<=n;i++)
    {
        if(maxim==lis[i])
        {
            fout<<a[i]<<" ";
            aux=lis[i];
            for(j=i+1;j<=n;j++)
                if(aux-1==lis[j])
                {
                    fout<<a[j]<<" ";
                    aux=lis[j];
                }
            return;
        }
    }
}
int main()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    Subsir();
    return 0;
}