Cod sursa(job #1982855)

Utilizator moltComan Calin molt Data 20 mai 2017 13:54:28
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n,v[100001],d[100001],max1 = -1,pozmax,aux[100001];
int main()
{
    in>>n;
    for (int i = 1; i <= n; ++i)
        in>>v[i];
    d[1] = 1;
    for (int i = 1; i <= n; ++i)
    {
        bool ok = 0;
        for (int j = 1; j <= i - 1; ++j)
            if (v[j] < v[i])
                {ok = 1;
                if (d[j] + 1 > d[i])
                    d[i] = d[j] + 1;}
        if (ok == 0)
            d[i] = 1;
    }
    for (int i = 1; i <= n; ++i)
        {if (d[i] > max1)
            {max1 = d[i];
            pozmax = i;}}
    out<<max1;
    int cnt = 1;
    aux[1] = v[pozmax];
    int poz = pozmax;
    for (int i = pozmax;i >= 1;--i)
         if (v[i] < v[poz])
             {aux[++cnt] = v[i];
             poz = i;}
    out<<endl;
    for (int i = cnt;i >= 1;--i)
         out<<aux[i]<<" ";
    return 0;
}