LIS (nlogn)

#define MAX_N 100100
int A[MAX_N], LIS[MAX_N];
int get_LIS(int A[], int n, int LIS[]){
  int L_idx[MAX_N], L_pre[MAX_N];
  int len = 0;
  int last = 0;
  for(int i = 0 ; i<n ; i++){
    // use upper_bound for longest non-decreasing sequence
    int pos = lower_bound(LIS, LIS+len, A[i]) - LIS; //first element greater or equal to A[i], or the end if there's none.
    LIS[pos] = A[i]; //LIS storest an increasing list with the same lenght of the actual LIS, but no necessarly the correct one.
    L_idx[pos] = i;  //L_idx stores the index in the orginal array A of the element in LIS[k].
    L_pre[i] = pos ? L_idx[pos -1] : -1; //L_pre[i] stores the index of the first previous element that is stricly smaller that A[i]
    if(pos==len) len++, last=i;
  }

  stack<int> s;
  for( ; last!=-1 ; last=L_pre[last]) s.push(A[last]); //Tracing back LIS elements
  for(int i=0 ; !s.empty() ; i++) LIS[i]=s.top(), s.pop(); //re-constructing LIS
  return len;
}