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.

view plainprint?

1. #define MAX_N 64  
2. int x[] = {4, 2, 3, 1, 5};  
3.   
4. int dp[MAX_N];  
5. int main() {  
6.     fill(dp, dp+MAX_N, INF);  
7.   
8.     REP(i, SIZE(x))  
9.         *lower_bound(dp, dp+MAX_N, x[i]) = x[i];  
10.   
11.     cout << lower_bound(dp, dp+MAX_N, INF) - dp << endl;  
12. }  

#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;
}