[Algospot] LIS (Longest Increasing Sequence)

Algospot

Longest Increasing Sequence

https://algospot.com/judge/problem/read/LIS

#include <stdio.h>
 
int n;
int lisarr[500], input[500];
int size;
 
void init()
{
    int i;
    for (i = 0; i < size; i++) {
        lisarr[i] = 0;
    }
    size = 0;
}
 
void lis(int num)
{
    int s, e, middle;
 
    if (size == 0 || lisarr[size - 1] <= num) {
        lisarr[size++] = num;
        return;
    }
 
    s = 0;
    e = size - 1;
 
    while (s <= e) {
        middle = (s + e) / 2;
 
        if (lisarr[middle] < num)        s = middle + 1;
        else            e = middle - 1;
    }
 
    lisarr[e + 1] = num;
}
 
int main()
{
    int nCount;
    int i, num;
 
    scanf("%d", &nCount);
 
    while (nCount--) {
 
        scanf("%d", &n);
 
        for (i = 0; i < n; i++) {
            scanf("%d", &input[i]);
        }
 
        for (i = 0; i < n; i++) {
            lis(input[i]);
        }
 
        printf("%d\n", size);
 
        init();
    }
 
    return 0;
}