Cod sursa(job #1687522)

Utilizator flibiaVisanu Cristian flibia Data 12 aprilie 2016 21:49:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

int main()
{
    long long n, a[100005], b[100005], c[100005], max, k, v1, v2, x1, x2;
    in >> n;
    for(int i = 1; i <= n; i++) in >> a[i];
    b[n] = 1;
    v1 = 0;
    if(n > 1)
        for(int i = n-1; i >= 1; i--)
            {
                max = 0;
                for(int j = i + 1; j <= n; j++) if(b[j] > max && a[j] > a[i]) 
                {
                    max = b[j];
                    c[i] = j;
                }
                b[i] = max + 1;
                if(b[i] > v1) 
                {
                    v1 = b[i]; v2 = i;
                }
            }
    out << v1 << "\n";
    while(b[v2] > 0)
    {
        if(b[v2] == 1) {out << a[v2]; break;}
        else
        {
            out << a[v2] << " ";
            v2 = c[v2];
        }
    }
    return 0;
}