I have talked about the $O(n^2)$ method of LIS before, This article will concentrate on the optimization.

As we know, there are several method to optimize the LIS from $O(n^2)$ to $O(n\log_{2}n)$. Segment tree is a good choice, which is not the best, but easist to understand.

In $O(n^2)$ method, we need to find the max value by going through it, as follow:

for (int i=1; i<n; ++i) {
  int max = 0;
  for (int j=0; j<i; ++j) {
    if(a[j] < a[i] && dp[j] > max) max = dp[j];
  }
  dp[i] = max + 1;
}

This will cost $O(n)$ to find the max of dp[0] to dp[i-1], which is not efficient.

So we use segment tree to maintain the max length of LIS end with the number i. That is to say, the segment[0, i-1] maintains the max length of LIS end with 0, 1, 2, …, i-1.

Hence we can find the max length of LIS end with i in $O(\log_{2}n)$ time.

Notice that the node of the segment tree represents a number in the original sequence, so we need to discretize if they are too big.

POJ 2533: