Approach

Algorithm

To find the Longest Increasing Subsequence (LIS), we use a 1D DP array where each element at position i stores the length of the LIS ending at index i of the array.

To make this DP array we can follow any of the approach that we learned while finding the length of the Longest Increasing Subsequence.

After computing the length of the Longest Increasing Subsequence (LIS) for each element using dynamic programming, start from the element with the maximum LIS value.
Initialize an empty list or string to store the LIS elements in reverse order.
From the element with the maximum LIS, move backward through the array to find elements that can form the LIS:
- For the current element, look for a previous element that is smaller and whose LIS value is exactly one less than the current element's LIS.
- Add that previous element to the LIS list and continue the process from that element.
Repeat this process until you reach the start of the LIS (where LIS value is 1).
Reverse the collected elements since they were collected backwards to get the actual LIS.