Cod sursa(job #1394266)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 20 martie 2015 10:17:47
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#define INF 1<<30
using namespace std;
std::vector< int > a,c;
std::vector< std::pair<int,int> > b;
int n,maxim,sirmaxim,k,x,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;
        k=0;
        for(int j=0;j<b.size();++j)
        {
            if(a[i]>a[ b[j].first ]&&maxim<b[j].second)
            {
                k = j;
                maxim = b[j].second;
            }
        }
        if(k!=0)
        {
            c.push_back(b[ k ].first);
            b[ k ].first = i;
            b[ k ].second += 1;
            if(sirmaxim<b[ k ].second)
            {
                sirmaxim = b[ k ].second;
                inceput = b[ k ].first;
            }
        }
        else
        {
            b.push_back( std::make_pair(i,1) );
            c.push_back(0);
            sirmaxim = 1;
        }

    }
    printf("%d\n",sirmaxim);
    afisare(inceput);
    return 0;
}