I have learned about this LIS problem and even implemented the O(N^2) solution.However am having problem grasping how to return the actual subsequence itself,specially when the explanation goes like "backtrack through the k array ".Could you suggest some good guides
3 Likes
First I explain O(n^2) solution and show how we can extend it to return actual longest subsequence.
Problem for LIS: we have sequence of numbers and we want to find subsequence, which is strictly increasing and as long as possible.
For each position i compute value lis(i), which is longest increasing subsequence with i-th element as last element of this subsequence. What we know about second element from end in our subsequence? It must be smaller than i-th element and it’s position is before position i. So we looking for such index j, that j < i, A[j] < A[i] (A[i] means value of element on i-th position) and lis(j) is as big as possible. Combining subsequence ending on position j and i-th element we obtain longest subsequence ending on position i.
Now for each index remembered one more thing - index j as back(i). So back(i) says us, on which index is previous element of longest subsequence ending on position i.
After that, it’s pretty obvious what we need to do. When we compute all values lis(i) and back(i) find the biggest value lis(i). This i is last element in our longest increasing subsequence. When we continue jumping by indexs back(i) we obtain our subsequence in reversed order.
This solution has complexity O(n^2) but idea with back links can be used even in better solutions and on other places as well.
Here you can check my solution. It reads sequence and write longest increasing subsequence. I hope, this helped you 
1 Like
@michal27 : Buggy line "A[j] < A[j] " .Kindly correct it.
Also do you know how to solve LIS using segment tree ?
@sandeeppandey: I dont if LIS problem can be solved using segment tree or not but there is an O(nlogn) solution for this problem which uses binary search.
Follow the below mentioned link.
For the second part, i.e. getting elements in LIS follow @michal27’s post.
@sandeepandey thanks. And yes I know how to find LIS using segment tree, I’ll write another answer for it.
So @sandeepandey wants to know, how to solve LIS problem in time O(n logn) using segment tree.
First thing, supposed, that if we have sequence of length n, than it only contains elements from 1 to n. If this is not fulfill, it can be easily repaired in O(n logn) using map (dictionary) or similar approach.
The idea is the same as in O(n^2) solution. We want to compute lis(i) - maximal length of subsequence ending with i-th element. Again, we want to find index j, such as j < i and A[j] < A[i] and lis(j) is as big as possible.
First condition must be met, because we only process smaller indexes. Now use second condition A[j] < A[i]. Create maximal segment tree, where on x-th position is pair of integer - longest subsequence ending with element x and last index k in this subsequence (so A[k] = x). Now we want to find maximal pair on segment [1, A[i]) (element A[i] is not included). And that easy with our segment tree. So if our maximum pair is (x_max, k_max) than lis(i) = x_max + 1 and back(i) = k_max.
Last thing is update position A[i] in our segment tree by pair (lis(i), back(i)). Note, that it’s possible that there is already bigger pair, so we don’t change anything.
I hope this is everything and now you understand it completly
2 Likes
@michal27 : Thanks 
I understood your idea.(Which i was thinking too.).Wht if input array will contains upper bound >=10^7 ?
As I mentioned you can repaired it. Just sort all elements in input array. Now replace first element with 1, second with 2 and so on. But if two elements are equal they should get same number. It’s not difficult to think, but implementation can be tricky.
If you hold on two hours (I must go somewhere now) I provide here sample code of how to do it.
Thankyou
Super Shiity Explanation