Cod sursa(job #1860906)

Utilizator AndreiITCuriman Andrei AndreiIT Data 28 ianuarie 2017 14:29:10
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int NMAX = 100005;
int n, v[NMAX], l[NMAX], urm[NMAX];
int main()
{
    in>>n;
    for(int i=1; i<=n; ++i)
        in>>v[i];
    l[n] = 1;
    urm[n] = 0;
    for(int i=n-1; i>=1; --i)
    {
        l[i] = 1;
        urm[i] = 0;
        for(int j=i+1; j<=n; ++j)
            if(v[i] < v[j] and l[i] < l[j] + 1)
            {
                l[i] = l[j] + 1;
                urm[i] = j;
            }
    }
    int sol = l[1], poz = 1;
    for(int i=1; i<=n; ++i)
        if(l[i] > sol)
        {
            sol = l[i];
            poz = i;
        }
    out<<sol<<'\n';
    while(poz!=0)
    {
        out<<poz<<' ';
        poz = urm[poz];
    }
    return 0;
}