Cod sursa(job #1919609)

Utilizator tidehyonBosoi Bogdan tidehyon Data 9 martie 2017 20:12:52
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001],pos[100001],lis[100001];
int n;

void Citire()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> v[i];
}

void PD()
{
    int maxim = 1, posm = n;
    lis[n] = 1;
    for(int i = n - 1; i >= 1; i--)
        for(int j = i + 1; j <= n; j++)
            if(v[i] < v[j] && lis[i] < lis[j] + 1)
            {
                    lis[i] = lis[j] + 1;
                    if(lis[i] > maxim)
                    {
                        maxim = lis[i];
                        posm = i;
                    }
            }
    for(int i = n - 1; i >= 1; i--)
        for(int j = i + 1; j <= n; j++)
            if(v[i] < v[j] && lis[i] == lis[j] + 1)
                    pos[i] = j;
    fout << maxim << "\n";
    fout << v[posm] << " ";
    while(lis[posm] != 1)
    {
        fout << v[pos[posm]] << " ";
        posm = pos[posm];
    }
}

int main()
{
    Citire();
    PD();
    return 0;
}