Cod sursa(job #831697)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 8 decembrie 2012 23:28:24
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<iostream>
#include<fstream>
#define N 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int x[N],LIS[N],Nr[N],Next[N],n;
int main()
{
    int i,poz,maxim,j,L,s=0;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>x[i];
    fin.close();
    LIS[n]=1;
    L=0;
    for(i=n-1;i>=1;i--)
    {
        maxim=0;
        poz=0;
        for(j=i+1;j<=n;j++)
            if(LIS[j]>maxim && x[i]<x[j])
            {
                maxim=LIS[j];
                poz=j;
            }
        Next[i]=poz;
        LIS[i]=maxim+1;
        L=LIS[i]>L?LIS[i]:L;
    }
    fout<<L<<"\n";
    for(i=1;i<=n;i++)
        if(LIS[i]==L)
        {
            j=i;
            while(Next[j]!=0)
            {
                fout<<x[j]<<" ";
                j=Next[j];
            }
            fout<<x[j]<<" ";
            fout<<"\n";
        }
    return 0;
}