好的，我将首先描述最简单的解决方案，即O（N ^ 2），其中N是集合的大小。还有一个O（N log
N）解决方案，我还将对此进行描述。在“高效算法”部分中在此处查找。

我将假设数组的索引从0到N-1。因此，我们将其定义DP[i]为以index为结尾的LIS（最长递增子序列）的长度i。为了进行计算，DP[i]我们查看所有索引j < i并检查是否DP[j] + 1>DP[i]和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]。该-1值是停止的标志。

好的，现在是更有效的O(N log N)解决方案：

让S[pos]被定义为结束长度的递增序列的最小整数pos。现在遍历X输入集的每个整数并执行以下操作：

1. 如果X>中的最后一个元素S，则追加X到的末尾S。这种本质意味着我们已经找到了一个新的最大的LIS。

2. 否则，发现在最小的元素S，这是>=比X，并改变它X。由于S可以随时进行排序，因此可以使用中的二进制搜索找到该元素log(N)。

总运行时间- N整数和每个整数的二进制搜索-N * log（N）= O（N log N）

现在让我们做一个真实的例子：

整数集合： 2 6 3 4 1 2 9 5 8

脚步：

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在LIS采用索引元素的结局i。

为了简化起见，我们可以将数组S（而不是实际的整数）保留在数组中，而是保留它们在集合中的索引（位置）。我们不保留{1, 2, 4, 5, 8}，但保留{4, 5, 3, 7, 8}。

即input [4] = 1 ，input [5] = 2 ，input [3] = 4 ，input [7] = 5
，input [8] = 8 。

如果我们正确更新父数组，则实际的LIS为：

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

现在重要的事情-我们如何更新父数组？有两种选择：

1. 如果X>中的最后一个元素S，则parent[indexX] = indexLastElement。这意味着最新元素的父元素是最后一个元素。我们只是X在的末尾添加前缀S。

2. 否则，发现在最小的元素的索引S，这是>=比X，并改变它X。在这里parent[indexX] = S[index - 1]。