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