好的，我将首先描述最简单的解决方案，即 O(N^2)，其中 N 是集合的大小。还存在一个 O(N log N) 解决方案，我也将对此进行描述。看here http://en.wikipedia.org/wiki/Longest_increasing_subsequence请参阅高效算法部分。
我假设数组的索引从 0 到 N - 1。所以让我们定义DP[i]以索引元素结束的 LIS（最长递增子序列）的长度i。计算DP[i]我们查看所有指数j < i并检查两个是否DP[j] + 1 > DP[i] and array[j] < array[i]（我们希望它不断增加）。如果这是真的，我们可以更新当前的最优值DP[i]。要找到数组的全局最优值，您可以从中获取最大值DP[0...N - 1].
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
我使用数组prev以便稍后能够找到实际序列而不仅仅是其长度。只需递归返回bestEnd在循环中使用prev[bestEnd]. The -1值是停止的标志。
好的，现在更高效O(N log N)解决方案：
Let S[pos]被定义为结束长度递增序列的最小整数pos。现在迭代每个整数X输入集并执行以下操作：
-
If X> 最后一个元素S，然后附加X到最后S。这本质上意味着我们已经找到了一个新的最大的LIS.
-
否则找到最小元素S，即>= than X，并将其更改为X。
因为S任何时候都已排序，可以使用二分查找找到该元素log(N).
总运行时间 -N整数并对每个整数进行二分搜索 - N * log(N) = O(N log N)
现在我们来做一个真实的例子：
整数集合：2 6 3 4 1 2 9 5 8
Steps:
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
所以LIS的长度是5（S 的大小）。
重建实际LIS我们将再次使用父数组。
让parent[i]是具有索引的元素的前驱i in the LIS以索引元素结束i.
为了让事情变得更简单，我们可以保留在数组中S，不是实际的整数，而是它们在集合中的索引（位置）。我们不保留{1, 2, 4, 5, 8}，但保留{4, 5, 3, 7, 8}.
即输入[4] =1，输入[5] =2，输入[3] =4，输入[7] =5，输入[8] =8.
如果我们正确更新父数组，实际的 LIS 是：
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
现在重要的是 - 我们如何更新父数组？有两种选择：
-
If X> 最后一个元素S, then parent[indexX] = indexLastElement。这意味着最新元素的父元素是最后一个元素。我们只是前置X到最后S.
-
否则找到最小元素的索引S，即>= than X，并将其更改为X. Here parent[indexX] = S[index - 1].
