Cod sursa(job #2474912)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 15 octombrie 2019 22:46:49
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <stdlib.h>
#define NMAX 100001
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
typedef struct BST
{
    int poz;
    BST *ST;
    BST *DR;
} arb;
int a[NMAX], n;
BST* insert(BST *arb, int poz)
{
    if(!arb)
    {
        arb = (BST*)malloc(sizeof(BST));
        arb -> poz = poz;
        arb -> ST = NULL;
        arb -> DR = NULL;
    }
    else if(a[arb -> poz] < a[poz]) arb -> DR = insert(arb -> DR, poz);
    else arb -> ST = insert(arb -> ST, poz);
    return arb;
}
int cnt(BST *arb)
{
    if(!arb -> DR) return 1;
    return 1 + cnt(arb -> DR);
}
BST* search(BST* arb, int key)
{
    if(arb == NULL || arb -> poz == key) return arb;
    if(a[arb -> poz] < a[key]) return search(arb -> DR, key);
    return search(arb -> ST, key);
}
void afisare(BST *arb)
{
    if(arb != NULL)
    {
        fout << a[arb -> poz] << " ";
        afisare(arb -> DR);
    }
}
int main()
{
    BST *arb = NULL, *arbf;
    fin >> n;
    for(int i = 1; i <= n; ++i)
    {
        fin >> a[i];
        arb = insert(arb, i);
    }
    int maxi = -1;
    for(int i = 1; i <= n; ++i)
    {
        BST *bs = search(arb, i);
        if(cnt(bs) > maxi)
        {
            maxi = cnt(bs);
            arbf = bs;
        }
    }
    fout << maxi << "\n";
    afisare(arbf);
    return 0;
}