Cod sursa(job #1380220)

Utilizator sabauandrei98Sabau Andrei sabauandrei98 Data 6 martie 2015 23:44:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <limits.h>
#include <cmath>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <map>
#include <fstream>
#include <list>
#include <iomanip>
#include <queue>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");
#define cin f
#define cout g

int i,j,n,v[100001],best[100001],prec[100001],where,maxim=LONG_MIN;

void dinamica()
{
    for(i=n-1; i>=1; i--)
        for(j=i+1 ; j<=n; j++)
            if (v[i] < v[j] && best[i] < best[j] + 1)
            {
                best[i] = best[j] + 1;
                prec[i] = j;
                if (best[i] > maxim ) maxim = best[i],where=i;
            }
}

void afisare()
{
    cout<<maxim + 1<<endl;
    while(where != -1)
        {
            cout<<v[where]<<" ";
            where = prec[where];
        }

}
int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>v[i];
        best[i] = 0;
        prec[i] = -1;
    }

    dinamica();
    afisare();

return 0;
}