PLEASE C++ ONLY The task is to find the length of the longest subsequence in a g

Question

PLEASE C++ ONLY

The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in ascending order.

For example, the length of the LIS for {15, 27, 14, 38, 26, 55, 46, 65, 85 } is 6 and the longest increasing subsequence is {15, 27, 38, 55, 65, 85}.

Input : arr[] = {3, 10, 2, 1, 20}

Output : Length of LIS = 3

The longest increasing subsequence is 3, 10, 20

Input : arr[] = {3, 2}

Output : Length of LIS = 1

The longest increasing subsequences are {3} and {2}

Input : arr[] = {50, 3, 10, 7, 40, 80}

Output : Length of LIS = 4

The longest increasing subsequence is {3, 7, 40, 80}

Rule:

Let, arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.

Then, L(i) can be recursively written as:

L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.

To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.

Assignment                                      (point: 20)

Follow the stated rules, complete the L = [....] array and find out what is the longest increasing subsequence for

arr = [100, 30, 90, 20, 29, 70, 109, 2, 22, 210, 55]

Show/Explain each step of filling L[i].

This is an open problem. You can use online resources to understand the problem. Then fill out the L array.

[Note: Do something similar that we have done in class for LCS problem in a worksheet filling out a 2D array

Arr= [20, 29, 70, 109, 210]

Length= 5

Explanation / Answer

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int a[]={50, 3, 10, 7, 40, 80};
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;
vector<int> v;
for(int k=end;k!=-1;k=b[k])
{
v.push_back(a[k]);
}
reverse(v.begin(), v.end());
for(int x: v) {
cout << x << ' ';
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.