Explained: Finding the Longest Increasing Subsequence using Segment Tree

Hey guys,

Well this is just random but i found out that for my most disappointment that the tutorials on the above topic arent really useful for the novice. Most tutorials just give the procedure in english or the code but not both. Hence I'm trying to write something human-understandable in the simplest english i know :D

Problem

Find the length of the longest increasing subsequence in a given array of integers
For the context of the tutorial we assume all integers are positive hence 0 will be our minimum.
Read more about in the wikipedia article


So the most obvious method is the complete search of the array which would take O(n^2) time. This is highly inefficient for a data set of very large n. Thus an alternative method should be used. Using the segment tree we can find the answer in just O(nlogn) time which is acceptable.

For those who aren't familiar with Segment Trees please refer to wikipedia or this Youtube tutorial. I actually found the Youtube tutorial quite informative and simple to understand.

So back to the solution, what we gonna do is to build segment tree and find the length of the longest subsequence. Please note that this won't give you the actual sequence but just the length of it. But you can implement the finding sequence part easily.

Procedure

1. Sort the original array but keep the original index of each element.
 
 original array  - the input array with the elements in their original order
 sorted array  -  an array of objects that contain information on the value of the element as well as its position in the original array. This array is sorted according to the value of the element.

2. Initialize the segment tree with all 0

2. We loop each element of the sorted array and in each iteration
      i. Take the original index of the element
      ii. Find the value corresponding to (0,index) from the segment tree. This would be 0 in initial iterations.
     iii. This value would be the length of longest subsequence upto that point, then add 1 to this value since obviously the current element has a value greater than all previous elements (since the array is sorted) and this extend the previous biggest sequence by 1.
     iv. Use this value to build the segment tree further. (update the tree)

Code

Let's look at the code and then I'll do some drawing and stuff to explain the process VISUALLY *_*



So it looks all okay till it comes to the loop. What eaxtly happend when the buildTree and findMax methods are called? How the tree is built?

Let's take our array, sorted array and the initial segment tree

Let's go through our loops

So finally the root of our tree gives the answer :D

Cyah