bal8099410227
BAN USER// longest_inc_subseq.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
using namespace std;
void find_subseq_n2_time(int *input,int n)
{
int *temp=new int[n];
int i,j;
int *path=new int[n];
for(i=0;i<n;i++)
{
temp[i]=1;
path[i]=i;
for(j=i-1;j>=0;j--)
{
if(input[j]<input[i] && temp[j]+1>temp[i])
{
path[i]=j;
temp[i]=temp[j]+1;
}
}
}
int max=temp[0];
for(i=0;i<n;i++)
{
if(temp[i]>max)
{
max=temp[i];
j=i;
}
}
cout<<"length of longest increasing subsequence is : "<<max<<" and path is : ";
cout<<j<<" ";
while(path[j]!=j)
{
cout<<path[j]<<" ";
j=path[j];
}
//cout<<path[j]<<endl;
cout<<endl;
}
template<class T>
int binsearch(T *input,int n,int index,int len,int *subseq_so_far)
{
int start=1;
int end=len;
int mid;
while(start<=end)
{
mid=start+((end-start)/2);
//cout<<"mid : "<<mid<<endl;
//if(mid==0)
//return ((input[index]>input[subseq_so_far[1]])?1:0);
if(input[subseq_so_far[mid]]==input[index])
return 0;
else if(input[subseq_so_far[mid]]>input[index])
end=mid-1;
else
start=mid+1;
}
return (start-1);
}
template<class T>
void find_subseq_nlogn(T *input,int n)
{
int *subseq_so_far;
int *path;
int i,j;
int length;
path=new int[n+1];
subseq_so_far=new int[n+1];
subseq_so_far[0]=-1;
subseq_so_far[1]=0;
length=1;
for(i=1;i<n;i++)
{
j=binsearch(input,n,i,length,subseq_so_far);
cout<<"index : "<<j<<endl;
path[i]=subseq_so_far[j];
if(j==length || input[i]<input[subseq_so_far[j+1]])
{
subseq_so_far[j+1]=i;
if(length<j+1)
length=j+1;
}
}
cout<<"length of the longest subsequence found is : "<<length<<endl;
cout<<"The path from end is : \n";
i=subseq_so_far[length];
while(i>=0)
{
cout<<input[i]<<" at index : "<<i<<endl;
i=path[i];
}
}
int main()
{
int input[]={99,100,100,100,101,3,4,5,6,7,8};
find_subseq_n2_time(input,11);
find_subseq_nlogn(input,11);
system("pause");
}
this contains both nlogn as well as n^2 time algos
- bal8099410227 June 24, 2012