c - 从数组中获取最大排序子数组的算法

Question

我正在尝试在 C 中做某事，我需要一个算法来返回另一个数组中包含的最大维度排序数组。因此，例如，如果我有以下数组：

A[5] = {5, 2, 3, 1, 4}

它应该返回：

2, 3, 4

而且我想不出任何有效的实施方式。有什么想法吗？谢谢你。:)

Answer 1

您的问题被称为“最长增加子序列”。

可以在此处找到利用动态规划的算法，并提供了很好的解释。它的最优渐近复杂度为O(nlogn)。

基本思想是，您跟踪具有长度的子序列的最佳可能最后一个元素（或者更确切地说是其索引）i。当您处理下一个元素时，您检查数组m以查看是否有

• 找到一个更好（即更小）可能的最后一个元素一定长度i
• 否则，您会发现比目前更长的序列。

Answer 2

从最长增加子序列的维基百科页面：

 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)

这不是 C，但应该很容易用 C 编写代码。