[dovelet][DP] LIS

dovelet

LIS

http://183.106.15.130/30stair/LIS/LIS.php?pname=LIS

C - 이진탐색 구현

#include <stdio.h>
 
int n;
int num[500000];
int parent[500000];
int lisArr[500000];
int size;
 
void lis(int idx)
{
    int s, e, middle;
 
    if (num[lisArr[size - 1]] < num[idx]) {
        parent[idx] = lisArr[size - 1];
        lisArr[size++] = idx;
        return;
    }
 
    s = 0; e = size;
    while (s <= e) {
        middle = (s + e) / 2;
        // 큰거 중에 가장 작은거랑 change
        if (num[lisArr[middle]] < num[idx])        s = middle + 1;
        else    e = middle - 1;                                             
    }
 
    if(e >= 0)    
        parent[idx] = lisArr[e];
    lisArr[e + 1] = idx;
}
 
void print(int p)
{
    if (p == -1)    return;
    print(parent[p]);
    printf("%d ", num[p]);
}
 
int main()
{
    int i, p;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        parent[i] = -1;
        scanf("%d", &num[i]);
    }
 
    lisArr[size++] = 0;
    for (i = 1; i < n; i++) {
        lis(i);
    }
 
    printf("%d\n", size);
    print(lisArr[size - 1]);
    printf("\n");
 
    return 0;
}