Cod sursa(job #1779276)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 15 octombrie 2016 00:08:40
Problema Subsir crescator maximal Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <stdlib.h>
#define MAX 100005
 
int bs(int* q, int l, int x);
void print(int* p, int* v, int n, int l);
 
int n, i, v[MAX], q[MAX], p[MAX], l;
 
int main(){
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d", &v[i]);
        p[i] = bs(q, l, v[i]);
        q[p[i]] = v[i];
        if(l < p[i])
            l = p[i];
    }
 
    printf("%d\n", l);
    print(p, v, n - 1, l);
    printf("\n");
    return 0;
}
 
int bs(int* q, int l, int x){
    int s = 1, d = l, m;
    if(l == 0)
        return 1;
 
    while(s < d){
        m = (s + d) / 2;
        if(q[m] == x)
            return m;
 
        if(q[m] > x){
            if(m == 1)
                return m;
            if(q[m - 1] < x)
                return m;
            else
                d = m - 1;
        }
 
        else
            s = m + 1;
    }
 
    if(s == d){
        if(q[s] == x)
            return s;
 
        if(q[s] > x){
            if(s == 1)
                return 1;
            if(q[s - 1] < x)
                return s;
            else
                return l + 1;
        }
 
        else
            return l + 1;
    }
}
 
void print(int* p, int* q, int n, int l){
    if(l <= 0) return;
 
    if(p[n] == l){
        print(p, q, n - 1, l - 1);
        printf("%d ", v[n]);
    }
    else
        print(p, q, n - 1, l);
}