LIS problem has a recursive solution and this also can be solved using DP.
Recursive solution:
#include <iostream>
#include <cstdlib>
using namespace std;
int lis(int arr[],int length,int *max_length)
{
if(length==1)
return 1;
int res,max_end_here=1;
//recursively we get all LIS those are ending with arr[0],arr[1]
//...and arr[length-1] and if max ending with arr[length-1]
//requires to be upadted then do it.
for(int i=1;i<length;i++)
{
res = lis(arr,i,max_length);
if(arr[i-1]<arr[length-1] && res+1>max_end_here)
max_end_here = res+1;
}
if(max_end_here>*max_length)
*max_length = max_end_here;
return max_end_here;
}
int main()
{
int sz,max_length;
int *arr;
cout<<"Enter size:\n";
cin>>sz;
cout<<"Enter elements:\n";
arr = (int*)malloc(sizeof(int)*sz);
for(int i=0;i<sz;i++)
{
cin>>arr[i];
}
max_length = 1;
lis(arr,sz,&max_length);
cout<<"LIS size = "<<max_length<<"\n";
free(arr);
return 0;
}
But the solution has overlapping substructure property The same solution is calculated more than once)it can be solved using DP.
DP Solution:
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
int DPLIS(int arr[],int length)
{
int *LIS_ANS;
LIS_ANS = (int*)malloc(sizeof(int)*length);
//memset(LIS_ANS,1,sizeof(LIS_ANS));
for(int i=0;i<length;i++)
LIS_ANS[i]=1;
for(int i=1;i<length;i++)
{
for(int j=0;j<i;j++)
{
if( arr[i]>arr[j] && LIS_ANS[i] < LIS_ANS[j]+1 )
LIS_ANS[i] = LIS_ANS[j]+1;
}
}
int mx = 2;
for(int i=0;i<length;i++)
if(mx<LIS_ANS[i])
mx = LIS_ANS[i];
free(LIS_ANS);
return mx;
}
int main()
{
int sz;
int *arr;
cout<<"Enter size:\n";
cin>>sz;
cout<<"Enter elements:\n";
arr = (int*)malloc(sizeof(int)*sz);
for(int i=0;i<sz;i++)
{
cin>>arr[i];
}
cout<<"LIS size = "<<DPLIS(arr,sz)<<"\n";
free(arr);
return 0;
}
Time complexity of this solution is O(N*N).
Better Solution with Time Complexity O(N*logN):
Lets assume A[] is an array of unsorted numbers. We keep track of active lists of LIS of different lengths. We only keep track of active lists of only one for each length, if we find more than one sequence of same length than we only keep the sequence having the smallest ending numbers. To design a O(N log N) algorithm following conditions are checked.
1) If A[i] is smallest of all ending numbers of existing active list, then start a new list keeping A[i] as first element new active list of length 1;
2) If A[i] is the largest of all the ending numbers of active list then clone the longest active list and add the number as last element.
3) If A[i] is in between smallest and largest ending elements of active lists then find an active list having the end element smaller than A[i] ,clone that active list, add A[i] at the end of that active list and discard the previous active list.
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <string.h>
#include <stack>
using namespace std;
int findIndex(int lis[],int upto,int val)
{
int low=-1,high=upto;
int mid;
while(high-low>1)
{
mid = low+(high-low)/2;
if(lis[mid]>=val)
high=mid;
else
low=mid;
}
return high;
}
int LIS(int arr[],int sz)
{
int *lis;
int *parent;
int len;
lis = (int*)malloc(sizeof(int)*sz);
parent = (int*)malloc(sizeof(int)*sz);
memset(lis, 0, sizeof(lis[0])*sz);
memset(parent, 0, sizeof(lis[0])*sz);
lis[0]=arr[0];
parent[0]=-1;
len=1;
for(int i=1;i<sz;i++)
{
if(arr[i]<lis[0])
{
lis[0]=arr[i];
}
else if(arr[i]>lis[len-1])
{
parent[i]=lis[len-1];
lis[len++]=arr[i];
}
else
{
int idx = findIndex(lis,len-1,arr[i]);
parent[i]=lis[idx-1];
lis[idx]=arr[i];
}
}
cout<<"Longest Increasing Subsequence is :\n";
stack<int> st;
for(int i=lis[len-1];i>=0;i=parent[i])
st.push(i);
while(!st.empty())
{
cout<<st.top()<<" ";
st.pop();
}
cout<<"\n";
delete[] lis;
delete[] parent;
return len;
}
int main() {
int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int sz = 16;
cout<<"LIS size = "<<LIS(arr,sz)<<"\n";
return 0;
}