Cod sursa(job #1919677)

Utilizator tidehyonBosoi Bogdan tidehyon Data 9 martie 2017 20:33:02
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[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--)
    {
        maxim = 0;
        for(int j = i + 1; j <= n; j++)
            if(v[i] < v[j])
                    maxim = max(maxim, lis[j]);
        lis[i] = 1 + maxim;
    }
    maxim = -1;
    for(int i = 1; i <= n; i++)
        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] << " ";

    bool ok;
    while(lis[posm] != 1)
    {
        ok = 0;
        for(int i = posm + 1; i <= n && !ok; i++)
        {
            if(v[i] > v[posm] && lis[i] == lis[posm] - 1)
            {
                ok = 1;
                posm = i;
                fout << v[posm] << " ";
            }
        }
    }
    fout << "\n";
}

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