It will be better if you guys can first discuss the top down recursive solution rather than straight away discussing the bottom up approach. It is really hard to visualise the bottom up approach, without knowing the recursive solution first. Please tell how to approach the question recursively.
Not understanding LIS
u can either include the current element provided it is smaller than the present element or u can opt to not select it
Optimal Substructure: 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:
To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
Formally, the length of the longest increasing subsequence ending at index i, will be 1 greater than the maximum of lengths of all longest increasing subsequences ending at indices before i, where arr[j] < arr[i] (j < i). Thus, we see the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems. The recursive tree given below will make the approach clearer:
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.