Longest Increasing Subsequence

// INPUT = {5,8,0,3,1,9,2,4}
// OUTPUT - Length of LIS = 4 {0,1,2,4} //prints only length
// Complexity - O(n^2)
// If anyone knows about the O(nlogn) solution, feel free to
// mention it in comments section

#include<stdio.h>
#include<stdlib.h>

int maxL(int *L,int i,int a[]){
int max = 0;
int j;
for(j=0;j<i;j++){
if(a[j] < a[i] && L[j] > max){
max = L[j];
}
}
return max;
}

int lis(int a[],int n){
int *L = (int *)malloc(sizeof(int)*n);
int i;
int lis = 1;
for(i=0;i<n;i++){
L[i] = maxL(L,i,a)+1;
}
for(i=0;i<n;i++){
if(L[i] > lis){
lis = L[i];
}
}
return lis;
}

int main(){
int a[] = {5,8,0,3,1,9,2,4};
int l = lis(a,sizeof(a)/sizeof(int));
printf("length of LIS = %d",l);
return 0;
}