[shkola] redica

Eto vi kod za namirane na naj-dylga rastqshta redica. S malki modifikacii
mozhe da se dokara do nenamalqvashta redica, no shte gi ostavq za uprazhnenie
(hint: nqma da stane ako prosto smenite `<' sys '<=' i '>' sys '>=' ;-)

-- 
Rangel Dokov



#include <stdio.h>

#define MAXN    100

// vryshta po-golqmoto ot 2 chisla
// za paskalistite da kazha che operatora `?:' si e chisto
// i prosto edin `if' napisan s po-malko simvoli ;-)
#define MAX(a,b) ( (a)>(b)?(a):(b) )

// tova mi e redicata ot chisla kakto mi e dadena
int str[MAXN];

// broj na elementite;
int count;

// v tozi masiv se zapisva naj-dobriq (t.e. naj-malkiq) kraj na redica
// s dylzhina `n'
int best_end[MAXN];
int best; // posledniq element na gorniq masiv kojto ne e 0

// tuk se zapisva poziciqta v redicata na koqto se namira tozi naj-dobyr
// kraj
int pos[MAXN];

// a tova pokazva roditelq na vseki element v naj-dobrata redica
// zavyrshasta s tozi element
int parent[MAXN];


void solve() {
        int i, l, r, m;

        best = 1;
        best_end[1] = str[1];
        pos[1] = 1;

        for (i = 2; i <= count; i++) {
                // standartno dvoichno tyrsene
                // tyrsim str[i] v masiva best_end
                l = 1; r = best; m = 1;
                while (l < r) {
                        m = (l+r)/2;
                        if (best_end[m] == str[i])
                                break;
                        if (best_end[m] < str[i])
                                l = ++m;
                        else
                                r = --m;
                }
                // kraj na standartnoto dvoichno tyrsene

                // tuk ima tri sluchaq za tova kyde ni e
                // ostavilo dvoichnoto tyrsene. Mislq che e qsno
                // ot if-ovete koi sa te
                if (best_end[m] == str[i])
                        parent[i] = parent[pos[m]];
                else if (best_end[m] > str[i] &&
                         ((m == 1) || (best_end[m-1] < str[i]))) {

                        // pos[0] e neizpolzvan element => pos[0] = 0
                        // m == 1 ne e specialen sluchaj
                        parent[i] = pos[m-1];
                        best_end[m] = str[i];
                        pos[m] = i;
                } else if (best_end[m] < str[i] &&
                           ((m == best) || (best_end[m+1] > str[i]))) {

                        parent[i] = pos[m];
                        best_end[m+1] = str[i];
                        pos[m+1] = i;
                        best = MAX(best, m+1);
                }
        }
}


/*
fomat na vhoda:
1 red sydyrzha edno chislo N - broq na chislata.
sledvashtite `N' reda sydyrzhat po edno chislo
*/
void input() {
        int i;

        scanf("%d", &count);
        for (i = 1; i <= count; i++)
                scanf("%d", &str[i]);
}


/*
naj-dylgata redica trqbva da se izvede na edin red sys po edin
interval mezhdu vseki 2 chisla.
*/
void print(int p) {
        if (parent[p] > 0)
                print(parent[p]);
        else {
                printf("%d", str[p]);
                return;
        }

        // slagame po edno intervalche predi vsqko chislo
        // (bez pyrvoto koeto se izvezhda s gorniq printf)
        printf(" %d", str[p]);
}

void output() {
        print(pos[best]);
        printf("\n");
}

int main() {
        input();
        solve();
        output();
        return 0;
}

Other related posts: