#include<bits/stdc++.h>
using namespace std;
int lis(int a[], int n)
{
int l[n], p[n], i, j, mx = 0, index = -1;
for(i=0;i<n;i++)
{
l[i] = 1;
p[i] = -1;
}
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i] > a[j] && l[i] < l[j]+1)
{
l[i] = l[j] + 1;
p[i] = j;
}
}
}
for(i=0;i<n;i++)
{
if(mx < l[i])
{
mx = l[i];
index = i;
}
}
cout << "\nLongest Increasing Subsequence is :: \n";
while(index >= 0)
{
cout << a[index] << " ";
index = p[index];
}
return mx;
}
int main()
{
int n, i;
cout << "Enter Array Size :: ";
cin >> n;
int a[n];
cout << "\nEnter Array Element :: \n";
for(i=0;i<n;i++)
cin >> a[i];
cout << "\n\nLongest Increasing Subsequence Size :: " << lis(a, n) << "\n";
return 0;
}
using namespace std;
int lis(int a[], int n)
{
int l[n], p[n], i, j, mx = 0, index = -1;
for(i=0;i<n;i++)
{
l[i] = 1;
p[i] = -1;
}
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i] > a[j] && l[i] < l[j]+1)
{
l[i] = l[j] + 1;
p[i] = j;
}
}
}
for(i=0;i<n;i++)
{
if(mx < l[i])
{
mx = l[i];
index = i;
}
}
cout << "\nLongest Increasing Subsequence is :: \n";
while(index >= 0)
{
cout << a[index] << " ";
index = p[index];
}
return mx;
}
int main()
{
int n, i;
cout << "Enter Array Size :: ";
cin >> n;
int a[n];
cout << "\nEnter Array Element :: \n";
for(i=0;i<n;i++)
cin >> a[i];
cout << "\n\nLongest Increasing Subsequence Size :: " << lis(a, n) << "\n";
return 0;
}
Comments
Post a Comment