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

Question

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

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

它应该返回:

2, 3, 4

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

Answer 1

您的问题称为“longest increasing subsequence”。

利用 dynamic programming 的算法可以是found here, with a good explanation .它具有 O(nlogn) 的最优渐近复杂度。

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

• 为某个长度 i
找到了更好(即更小)可能的最后一个元素
• 否则你会找到一个比目前更长的序列。