#include<iostream>
using namespace std;
int main()
{
int a[]={0,8,4,12,2,10,6,1,9,5,13,3,11,7};
int b[50],i,j,n,ls[50];
n=sizeof(a)/sizeof(a[0]);
int maxlen=0,end=-1;
b[0]=-1;
for(i=0;i<n;i++)
{
ls[i]=1;
for(j=0;j<i;j++)
{
if(a[i]>a[j] && ls[i]<ls[j]+1)
{
ls[i]=ls[j]+1;
b[i]=j;
}
}
if(ls[i]>maxlen)
{
end=i;
maxlen=ls[i];
}
}
cout<<maxlen<<endl;
for(int k=end;b[k]!=-1;k=b[k])
{
cout<<a[k];
}
return 0;
}
This was the program I done for finding the longest increasing subsequence. I am getting the length of the subsequence correctly but i am not getting the sequence correctly. I think there may be a problem with the the last for loop which contains the variable k
, but I cant figure it out. please help me.