Cod sursa(job #893343)

Utilizator SebiDDanila Sebastian SebiD Data 26 februarie 2013 15:08:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <algorithm>
using namespace std;

int v[100005], d[100005], n, m, mi;
int t[100005];

//6
//v = 1 5 2 4 9 0
//d = 1 2 2 3 4 1

ofstream fout ("scmax.out");

void Write (int x)
{
    if (t[x] != -1)
        Write (t[x]);
    fout << v[x] << " ";
}

int main ()
{
    ifstream fin ("scmax.in");
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        d[i] = 1;
        t[i] = -1;
        for (int j = 1; j < i; ++j)
            if (d[j] + 1 > d[i] && v[i] > v[j])
            {
                d[i] = d[j] + 1;
                t[i] = j;
                if (m < d[i])
                {
                    m = d[i];
                    mi = i;
                }

            }
    }
    fout << m << "\n";
    Write (mi);
    fout.close ();
    return 0;
}