#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int lis( int* a, int N ) {
  int *best, i, j, max = INT_MIN;
  best = (int*) malloc ( sizeof( int ) * N );
  for ( i = 0; i < N; i++ ) best[i] = 1;
    for ( i = 1; i < N; i++ )
      for ( j = 0; j < i; j++ )
      {   if ( a[i] > a[j] && best[i] < best[j] + 1 )
          {  best[i] = best[j] + 1;
            if(max < best[i])
                  max = best[i];}         
       }
   return max;
}
int main(){
  int b[] = { 1, 3, 2, 4, 3, 5, 4, 6 };  printf("%d\n", lis( b, 8 ) );}

I2luY2x1ZGUgPGxpbWl0cy5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgppbnQgbGlzKCBpbnQqIGEsIGludCBOICkgewogIGludCAqYmVzdCwgaSwgaiwgbWF4ID0gSU5UX01JTjsKICBiZXN0ID0gKGludCopIG1hbGxvYyAoIHNpemVvZiggaW50ICkgKiBOICk7CiAgZm9yICggaSA9IDA7IGkgPCBOOyBpKysgKSBiZXN0W2ldID0gMTsKICAgIGZvciAoIGkgPSAxOyBpIDwgTjsgaSsrICkKICAgICAgZm9yICggaiA9IDA7IGogPCBpOyBqKysgKQogICAgICB7ICAgaWYgKCBhW2ldID4gYVtqXSAmJiBiZXN0W2ldIDwgYmVzdFtqXSArIDEgKQogICAgICAgICAgeyAgYmVzdFtpXSA9IGJlc3Rbal0gKyAxOwogICAgICAgICAgICBpZihtYXggPCBiZXN0W2ldKQogICAgICAgICAgICAgICAgICBtYXggPSBiZXN0W2ldO30gICAgICAgICAKICAgICAgIH0KICAgcmV0dXJuIG1heDsKfQppbnQgbWFpbigpewogIGludCBiW10gPSB7IDEsIDMsIDIsIDQsIDMsIDUsIDQsIDYgfTsgIHByaW50ZigiJWRcbiIsIGxpcyggYiwgOCApICk7fQ==