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.

 

My Code:

// 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!!!!
**********************************/