Introduction
Finding a subsequence of a given sequence with elements sorted from lowest to highest and with the greatest possible length is known as the Longest Increasing Subsequence problem. This sequence need not be continuous or exclusive.
For instance, [0, 2, 6, 9, 11, 15] is the longest growing subsequence of [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]. The input sequence lacks any rising subsequences with 7 members, and this subsequence has 6 length. In this case, the longest growing subsequence is not the only one. For instance, the rising subsequences [0, 4, 6, 9, 11, 15] or [0, 4, 6, 9, 13, 15] are the same input sequence's other equal-length growing subsequences.
Please take notice that the issue primarily focuses on subsequences that aren't needed to be continuous, meaning that they don't have to line up in order inside the original sequences.
Optimal Substructure (Dynamic Problem)
There is an optimal substructure for the issue. This means that the issue may be reduced into more manageable, straightforward "subproblems," which can then be turned into even more manageable, straightforward subproblems, until the issue's solution is easy. Additionally, the aforementioned approach displays overlapping issues. The same subproblems are calculated again, as seen by the recursion tree of the answer. Dynamic programming can be used to solve issues with optimum substructure and overlapping subproblems by memoizing rather than continually computing the subproblem solutions. The top-down method is used in the memoized version because we first divide the problem into smaller problems before computing and storing values.
Bottom Up Efficient Solution
This issue can also be resolved from the bottom up. When using the bottom-up method, start by resolving minor subproblems before moving on to larger ones. With the bottom-up method described below, L[i], which holds the length of the longest ascending subsequence of subarray arr[0...i] that ends with arr[i], is computed for each 0 = I n. Consider the LIS of all lower values of I (let's say j) that have previously been computed and choose the highest L[j], where arr[j] is less than the current element arr[i]. This will provide L[i]. It doesn't incur recursion overhead but has the same asymptotic runtime as Memoization.
Code
Complexity Analysis
The above code has an O(n^2) time complexity and takes up an extra O(n^2) of memory, where n is the length of the provided sequence.