好的，我将首先描述最简单的解决方案，即 O(N^2)，其中 N 是集合的大小。还有一个 O(N log N)
的解决方案，我也会描述。在高效算法部分中查找它。

我将假设数组的索引是从 0 到 N - 1。所以让我们定义DP[i]为 LIS（最长递增子序列）的长度，它在 index
的元素处结束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]。