Cod sursa(job #1158830)

Utilizator florin.ilieFlorin Ilie florin.ilie Data 29 martie 2014 09:40:47
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct nod{
    int x;
    int lung;
    nod *st,*dr;
}*rad;

int n,mx,x;
vector <int> sol;

void adaugare (nod *&q,int nr,int lung)
{
    if(!q){
        q=new nod;
        q->x=nr;
        q->lung=lung;
        if(mx<lung)
            mx=lung;
        return;
    }
    if(q->x>=nr)    adaugare(q->st,nr,1);
    else            adaugare(q->dr,nr,lung+1);
}

int cautare (nod *q){
    if(q->lung==mx){
        sol.push_back(q->x);
        return 1;
    }
    if(q->st && cautare(q->st))  return 1;
    if(q->dr &&cautare(q->dr)){
        sol.push_back(q->x);
        return 1;
    }
    return 0;
}

int main()
{
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");
    fin>>n;
    vector <int> sir;
    for(int i=0;i<n;i++){
        fin>>x;
        adaugare(rad,x,1);
    }
    cautare(rad);
    fout<<mx<<'\n';
    for(mx--;mx>=0;mx--){
        fout<<sol[mx]<<' ';
    }
    fout<<'\n';
    return 0;
}