http://ideone.com/Vzvbyu

vector<int> d;
int ans, n;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        vector<int>::iterator it = upper_bound(d.begin(), d.end(), x);
        if (it == d.end()) d.push_back(x);
        else *it = x;
    }
    printf("LIS = %d", d.size());
    return 0;
}

I think this will be helpful.

I have a very short implementation:

  int n, a[N], b[N], f[N], answer=0;
  ... // enter n and a[] from keyboard

  for (int i=1; i<=n; i++){
      f[i]=lower_bound(b+1, b+answer+1, a[i])-b;
      maximize(answer, f[i]);
      b[f[i]]=a[i];
   }

   printf("%d\n", answer);

If you want to print the LIS:

   vector<int> T;

   int require = answer;
   for (int i=n; i>=1; i--)
   if (f[i]==require){
      T.push_back(a[i]);
      require--;
   }
   // then print T with reversed order
   int i=T.size();
   while (i--) printf("%d ", T[i]);
   printf("\n");

I've learned it from this video https://www.youtube.com/watch?v=S9oUiVYEq7E

It's very well explained. My code:

#include <stdio.h>

int a[10001], t[10001], n, l, i;

/**
a -> This is the input, is an array of integers
t -> Each position have the index of the last item in the ith LIS
l -> The last valid position of t
n -> Size of input a
**/

int ceil(int v)
{
    int init = 0, fin = l; ///Start and end for binary search
    while(init < fin-1)
    {
        int m = (init+fin)/2;
        
        if(a[t[m]] >= v)
            fin = m;
        else
            init = m;
    }

    if(a[t[init]] >= v)
        return init;
    return fin;
}

void lis()
{
    r[0] = 1;
    t[0] = 0;
    l = 0;

    for(i=1; i<n; i++)
    {
        if(a[i] > a[t[l]])
            l++, t[l] = i;
        else
            t[ceil(a[i])] = i;
    }
}