学步园

问题：找出一个n个数的序列X中最长的单调递增子序列。

分析1：
这里描述一个O(n^2)的算法，令c[i]表示：在a[0->i]中，当以a[i]为单调递增子序列最后一个元素时，所得最长单调递增子序列的长度。所以，我们可以得到递推式：

代码：

#include <iostream><br /> #define MAXLENGTH 1000<br /> using namespace std;<br /> /**<br /> * @brief Get the longest increasing subsequence. The time complexity is O(n^2).<br /> *<br /> * @param X[]: the sequence X. Index from 0 to n-1<br /> * @param n: the length of X<br /> * @param c[]: c[i] means the longest increasing subsequence of X[0->i] when regard X[i] as the last element of increasing subsequence<br /> * @param line[]: the path of the longest increasing subsequence<br /> *<br /> * @return The longest increasing subsequence's length<br /> */<br /> int LongestIncreasingSubsequence(int X[], int n, int c[], int line[])<br /> {<br /> //path[i] point to the index of pre-element of i's element<br /> int path[MAXLENGTH];<br /> for (int i = 0; i < n; ++i)<br /> {<br /> path[i] = i;<br /> }<br /> c[0] = 1;<br /> //construct c[][]<br /> for (int i = 1; i < n; ++i)<br /> {<br /> c[i] = 1;<br /> for (int j = 0; j < i; ++j)<br /> {<br /> if (X[i] >= X[j] && c[j] + 1 > c[i])<br /> {<br /> c[i] = c[j] + 1;<br /> path[i] = j;<br /> }<br /> }<br /> }<br /> int max = 0;<br /> int end = -1;<br /> //get max and get the index of longest increasing subsequence's last element<br /> for (int i = 0; i < n; ++i)<br /> {<br /> if (c[i] > max)<br /> {<br /> max = c[i];<br /> end = i;<br /> }<br /> }<br /> int i = 1;<br /> //get the longest increasing subsequence<br /> line[0] = X[end];<br /> while (path[end] != end)<br /> {<br /> line[i++] = X[path[end]];<br /> end = path[end];<br /> }<br /> return max;<br /> }<br /> int main()<br /> {<br /> int n;<br /> int X[MAXLENGTH];<br /> int c[MAXLENGTH];<br /> int line[MAXLENGTH];<br /> while (cin >> n, n != 0)<br /> {<br /> for (int i = 0; i < n; ++i)<br /> {<br /> cin >> X[i];<br /> }<br /> int max = LongestIncreasingSubsequence(X, n, c, line);<br /> cout << "Longest Increasing Subsequence's Length: " << max << endl;<br /> for (int i = max - 1; i >= 0; --i)<br /> {<br /> cout << line[i];<br /> }<br /> cout << endl;<br /> }<br /> }<br />

分析2：
这里描述一个O(n*log(n))的算法，令c[i]代表：长度为i的单调递增子序列的最后一个元素在X中的位置。当一个新元素进来，生成新的长度为i的单调递增序列时，会覆盖掉c[i]，从而保证c[i]尽量小。

代码：

#include <iostream><br /> #define MAXLENGTH 1000<br /> using namespace std;<br /> /**<br /> * @brief Get the position of x in c[]<br /> *<br /> * @param c[]: the c[] which has the same meaning of LongestIncreasingSubsequence<br /> * @param len: the length of c[]<br /> * @param i: the i<br /> * @param X[]: the sequence X<br /> *<br /> * @return The i's position<br /> */<br /> int GetPosition(int c[], int len, int i, int X[])<br /> {<br /> int start = 1;<br /> int end = len;<br /> while (start <= end)<br /> {<br /> int mid = (start + end) / 2;<br /> if (X[c[mid]] <= X[i])<br /> {<br /> start = mid + 1;<br /> }<br /> else<br /> {<br /> end = mid - 1;<br /> }<br /> }<br /> return start;<br /> }<br /> /**<br /> * @brief Get the longest increasing subsequence. The time complexity is O(n*log(n)).<br /> *<br /> * @param X[]: the sequence X. Index from 0 to n-1<br /> * @param n: the length of X<br /> * @param c[]: c[i] means the last element's index in increasing subsequence whose length is i. If there are several subsequence whose length is i, c[i] should be the least one's index<br /> * @param path[]: record the elements' indexs in the longest increasing subsequence<br /> *<br /> * @return The longest increasing subsequence's length<br /> */<br /> int LongestIncreasingSubsequence(int X[], int n, int c[], int path[])<br /> {<br /> c[0] = -1;<br /> c[1] = 0;<br /> int line[MAXLENGTH];<br /> //line[i] == -1 means that i is the first element's index int the increasing subsequence<br /> line[0] = c[0];<br /> int len = 1;<br /> for (int i = 1; i < n; ++i)<br /> {<br /> int index = GetPosition(c, len, i, X);<br /> //c[index - 1] is the pre-element's index of element i<br /> line[i] = c[index - 1];<br /> c[index] = i;<br /> if (index > len)<br /> {<br /> len = index;<br /> }<br /> }<br /> //get the path<br /> path[0] = c[len];<br /> int i = 0;<br /> while (line[path[i]] != -1)<br /> {<br /> path[i + 1] = line[path[i]];<br /> ++i;<br /> }<br /> return len;<br /> }<br /> int main()<br /> {<br /> int n;<br /> int X[MAXLENGTH];<br /> int c[MAXLENGTH];<br /> int path[MAXLENGTH];<br /> while (cin >> n, n != 0)<br /> {<br /> for (int i = 0; i < n; ++i)<br /> {<br /> cin >> X[i];<br /> }<br /> int max = LongestIncreasingSubsequence(X, n, c, path);<br /> cout << "Longest Increasing Subsequence's Length: " << max << endl;<br /> for (int i = max - 1; i >= 0; --i)<br /> {<br /> cout << X[path[i]];<br /> }<br /> cout << endl;<br /> }<br /> }<br />