Cod sursa(job #933429)

Utilizator annnaVoicila Ana Maria annna Data 29 martie 2013 23:04:45
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<iostream>
#include<fstream>

using namespace std;

ifstream f("sir.in");

int a[100],aux[100],b[100],c=1;

int caut(int x)
{
    int p=1,q=c,m;
    if(a[b[q]]<x) return q+1;
    while(p<q)
    {
        m=(p+q)>>1;
        if(a[b[m]]>=x) q=m;
        else p=m+1;
    }
    return q;
}

void afiseaza(int x)
{
    if(aux[x]>0)
        afiseaza(aux[x]);
    cout<<aux[x]<<" ";
}

int main(){
    int i,poz,maxm=0,imax,n;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    b[1]=1;
    for(i=2;i<=n;i++)
        {
        poz=caut(a[i]);
        aux[i]=b[poz-1];
        b[poz]=i;
        if(poz>c) c++;
        if(poz>maxm) {
            maxm=poz;
            imax=i;
        }
    }
   cout<<maxm<<endl;
    afiseaza(imax);
f.close();
return 0;
}