Cod sursa(job #1394241)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 20 martie 2015 09:54:24
Problema Subsir crescator maximal Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#define INF 1<<30
using namespace std;
std::vector< int > a,b,c;
int n,maxim,sirmaxim,x,pre,inceput;
void afisare(int pre)
{
    if(c[ pre ]!=0)afisare(c[pre]);
    printf("%d ",a[ pre ]);
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&x);
        a.push_back(x);
        maxim = 0;
        pre = 0;
        for(int j=0;j<b.size();++j)
        {
            if(b[j]>maxim&&a[j]<a[i])
            {
                maxim = b[j];
                pre = j;
            }
        }
        if(maxim+1>sirmaxim)
        {
            inceput = i;
            sirmaxim = maxim+1;
        }
        b.push_back(maxim+1);
        c.push_back(pre);
    }
    printf("%d\n",sirmaxim);
    afisare(inceput);
    return 0;
}