Page List

Search on the blog

2011年1月24日月曜日

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


0 件のコメント:

コメントを投稿