Cod sursa(job #1911230)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 7 martie 2017 19:50:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int n, a[100005], lis[100005];

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

void Rezolva()
{
    int i, j, maxim, poz;
    /// lis[i] = 1 + max(lis[j]), unde j>i si a[j] > a[i]

    lis[n] = 1;
    for (i=n-1; i>=1; i--)
    {
        maxim = 0;
        for (j=i+1; j<=n; j++)
            if (a[j] > a[i])
                maxim = max(maxim, lis[j]);
        lis[i] = 1 + maxim;
    }
/// afisare termeni

    maxim = -1;
    for (i=1; i<=n; i++)
    {
        if (lis[i] > maxim)
        {
            maxim = lis[i];
            poz = i;
        }
    }
    fout << maxim << "\n";
    fout << a[poz] << " ";
    int ok;
    while (lis[poz] != 1)
    {
        /// cauta urmatorul poz
        ok = 0;
        for (j=poz+1; j<=n && ok==0; j++)
        {
            if (a[j] > a[poz] && lis[j] == lis[poz]-1)
            {
                ok=1;
                poz=j;
                fout << a[poz] << " ";
            }
        }
    }
    fout << "\n";
}

int main ()
{
    int i, j;
    Citire();
    Rezolva();
    fin.close();
    fout.close();
    return 0;
}