Cod sursa(job #1210501)

Utilizator dianaa21Diana Pislaru dianaa21 Data 20 iulie 2014 09:40:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
using namespace std;
ifstream is ("scmax.in");
ofstream os ("scmax.out");
int n;
long long v[100001], L[100001], mx, maxim, t;
int main()
{
    is >> n;
    for(int i = 1; i <= n; ++i)
        is >> v[i];
    L[n] = 1;
    for(int k = n-1; k >= 1; --k)
    {
        mx = 0;
        for(int i = k+1; i <= n; ++i)
        {
            if(v[i] > v[k] && L[i] > mx)
                mx = L[i];
        }
        L[k] = mx+1;
        if(L[k] > maxim)
            maxim = L[k], t = k;
    }
    os << maxim << '\n';
    os << v[t] << ' ';
    for(int i = t+1; i <= n; ++i)
        if(v[i] >= v[t] && L[i] == maxim-1)
            os << v[i] << ' ', maxim--;
    is.close();
    os.close();
    return 0;
}