An impressive code(1)

Now I'm studying DP.

And I encountered a wonderful code.

It's a solution to LIS, longest increasing sequence, which is a classic DP problem where you are to find the longest subsequence {a_{i1}, a_{i2}, .... a_{im}} from a given sequence {a_0, a_1, a_2, .... a_n}, such that i1 < i2 < , ..., im and a_{i1} < a_{i2} < , ...., a_{im} hold.

I was able to solve the problem, but the sample code in my textbook was so great. I was thrilled!!

Here's the source code.

In this manner, You can solve LIS at the order of nlog(n).

Notice that the STL function lower_bound() works at log(n) since the internal structure is a binary tree.

#define MAX_N 64
int x[] = {4, 2, 3, 1, 5};

int dp[MAX_N];
int main() {
    fill(dp, dp+MAX_N, INF);

    REP(i, SIZE(x))
        *lower_bound(dp, dp+MAX_N, x[i]) = x[i];

    cout << lower_bound(dp, dp+MAX_N, INF) - dp << endl;
}