**Longest Increasing Subsequence (LIS)**

Last Update: 16 April, 2009

**Problem:** The longest increasing subsequence
problem is to find a subsequence of a given sequence in which
the subsequence elements are in sorted order, lowest to highest,
and in which the subsequence is as long as possible. This
subsequence is not necessarily contiguous. Longest increasing
subsequences are studied in the context of various disciplines
related to mathematics, including algorithmics, random matrix
theory, representation theory, and physics. The longest
increasing subsequence problem is solvable in time O(n log n),
where n denotes the length of the input sequence. Here, is an
implementation in O(n log n) time.

```
// C++ Code for LIS - Longest increasing subsequenc
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define CLEAR(a) memset(a,0,sizeof(a))
using namespace std;
const int neg_infinite=-1047483648;
int input[1000000];
void binary_search(int start, int end, int key)
{
int mid;
while(start<=end)
{
mid=(start+end)/2;
if(input[mid] == key)
return;
else if(input[mid] > key)
end=mid-1;
else
start=mid+1;
}
if(input[start]<key) // no need; just for safety!
start++;
input[start]=key;
}
main()
{
// freopen("input.txt","rt",stdin)
// freopen("out.txt","wt",stdout)
int i,n,cur,num,set=1;
while(scanf("%d",&n)==1 && n!=0)
{
cur=0;
input[0]=neg_infinite;
for(i=1;i<=n;i++)
{
scanf("%d",&num);
if(num > input[cur])
{
cur++;
input[cur]=num;
}
else if(num < input[cur])
{
binary_search(0,cur,num);
}
}
printf("Set %d: %d\n",set++,cur);
}
return 0;
}
/*** Programmed by:
###########################
## ~ ORONNO ~ ##
## Team-: "Gladiator" ##
## CSEDU 12th Batch. ##
###########################
Note: This program is not totally
useless. Because, at least, this
might be used as a bad example!!!!
**********************************/
```