how to construct all LIS

[phoenix]

Code: Select all

#include<iostream>
#define INF 1<<20
#define min(a,b) (a<b?a:b)
#define MAX 100
using namespace std;

int B[]={-INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};

int bin(int key)
{
	int v;
	int lo=0;
	int hi=11;
	int mid;
	while(lo<=hi)
	{
		mid=lo+(hi-lo)/2;
		if(B[mid]>key)
		{
			v=mid;
			hi=mid-1;
		}
		else
			lo=mid+1;
	}
	return v;
}

int main()
{
	
	int i;
	int arr[]={9,2,5,4,3,7,11,8,10,13,1};

	int max=-1;
	for(i=0;i<11;i++)
	{
		int pos=bin(arr[i]);
		B[pos]=arr[i];
		if(max<pos)max=pos;
	}
	cout<<max<<endl;
	return 0;
}

i am using this nlgk algorithm to print the length of LIS of arr[].how can i print all LIS ??

[Jan]

After finding the B[] values for all items in arr[], you can find the max in B[]. Say its index is i.

Then the algorithm would be

1) Check from i - 1 to 0 and find the item j such that arr[j] < arr, and B[j] = B - 1.
2) Let i = j and go to step 1.

Using this procedure you can find a sequence. For all sequences you can use the same idea. Just think a bit.

[zobayer]

Thanks to Jan vai, it helped