Cod sursa(job #1798716)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 5 noiembrie 2016 13:03:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n,i,v[100001],x[100001],j,maxim,u;
int k,indice,v2[100001];

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

    for(i=1;i<n;i++)
    {
        j=i;
        maxim=0;
        for(j=i;j>=0;j--)
        {
            if(v[j]<v[i] and maxim<x[j])
            {
                maxim=x[j];
            }
        }
        x[i]=maxim+1;
    }
    maxim=0;
    for(i=0;i<n;i++)
    {
        if(maxim<x[i])
        {
            maxim=x[i];
            indice=v[i];
            u=i;
        }
    }
    v2[0]=indice;
    k=1;
    for(i=u-1;i>=0;i--)
    {
        if(v[i]<indice and x[i]==x[u]-1)
        {
            v2[k]=v[i];
            k++;
            indice=v[i];
            u=i;
        }
    }
    fout << maxim << endl;
    for(i=k-1;i>=0;i--)
        fout << v2[i]<< ' ';


    return 0;
}