HW3_lis

#include <cstdio>
#include <cstdlib>

int find_lis(int* a, int* b, int n)
{
    int* p = (int*)malloc(n*sizeof(int));
    int u = 0, v = 0, j = 0;
    b[0] = 0;

    for (int i = 1; i < n; i++)
    {
        if (a[b[j]] < a[i])
        {
            p[i] = b[j];
            j++;
            b[j] = i;
            continue;
        }
        for (u = 0, v = j; u < v;)
        {
            int c = (u + v) / 2;
            if (a[b[c]] < a[i])
                u=c+1;
            else
                v=c;
        }
        if (a[i] < a[b[u]])
        {
            if (u > 0)
                p[i] = b[u-1];
            b[u] = i;
        }
    }

    for (u = j + 1, v = b[j]; u--; v = p[v])
        b[u] = v;

    return j;
}


int main()
{
    int n = 0;
    scanf("%d", &n);
    int* arr = (int*)malloc(n*sizeof(int));
    for (int i = 0; i < n; i++)
        scanf("%d", &seq[i]);
    int* lis = (int*)malloc(n*sizeof(int));
    int j = find_lis(arr, lis, n);

    for (size_t i = 0; i <= j; i++)
        printf("%d ", arr[lis[i]]);
    printf("\n");

    return 0;
}