Cod sursa(job #2062764)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 10 noiembrie 2017 20:16:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
//http://www.infoarena.ro/problema/scmax       Subsir crescator maximal
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n, v[100005],mx,b[100005],sol[100005], l,rez;
void best(int arr[]);
void construire();
int main()
{
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    best(v);
    construire();
    fout << rez <<"\n";
    for(int i=1; i<=rez; i++)
        fout << sol[i] << " ";
}
void best(int arr[])
{
    b[1]=1;
    for(int i=2; i<=n; i++)
        {
            mx=0;
            for(int j=1; j<=i-1; j++)
            {
                if(arr[j]<arr[i] && mx<b[j])
                    mx=b[j];
            }
            b[i]=mx+1;
        }
}

void construire()
{
    int m=1;
    for(int i=2; i<=n; i++)
        if(b[i]>b[m])
            m=i;
    l=b[m];
    rez=l;
    sol[l]=v[m];
    int i;
    while(b[m]>1)
    {
        i=m-1;
        while(v[i]>=v[m] || b[i]!=b[m]-1)
            i--;
        m=i;
        l--;
        sol[l]=v[m];
    }
}