数组中最长的凸子序列

Question

假设我们给出了一个整数输入数组,如何找到满足以下条件的最长凸子序列:

c[i] < (c[i-1] + c[i+1]) / 2

c[i-1],c[i]并且c[i+1]是子序列中的三个连续元素.

例如,如果输入数组是{ 1, 2, -1, 0, 3, 8, 5 },则最长的凸子序列应为:{ 1, -1, 0, 3, 8 }或{ 2, -1, 0, 3, 8 }.

我试图在"最长增加子序列"(LIS)问题中使用相同的动态编程思想来解决这个问题.但是因为子序列中的每个元素都依赖于前两个元素,所以似乎O(n ^ 2)解决方案是不可能的.谢谢您的帮助.

Answer 1

这是 O(N ² log N) 算法（因为log N这里只是因为排序，所以我们可以使用不同的排序算法或更高级的优先级队列将其减少到 O(N ² log log N) 甚至 O(N ² )） :

1. 为每对输入数组元素创建一个数组：P[]。每对内的元素按其索引排序。
2. 根据值差异对这些对进行排序Y2 - Y1。如果Y2 - Y1值相等，则应按第二个索引按降序对它们进行排序。
3. L[]对以索引 0 .. N-1 结尾的子序列的子序列长度数组进行零初始化。
4. 对于每对来自P[]（按排序顺序）：L[X2] = max(L[X2], L[X1] + 1)。其中X是输入数组中元素的索引。
5. 求 中的最大值L[]。这是最长凸子序列的长度。
6. 为了能够重建子序列本身，步骤 #4 还应该更新反向指针链。当L[X2]更新时，我们将创建一个指向 对应的条目所指向的节点的节点，然后将对应于这个新节点的X1条目指向： 。X2BP_Head[X2] = new Node(BP_Head[X1])

凸性质c[i] < (c[i-1] + c[i+1]) / 2可以转化为等价不等式c[i] - c[i-1] < c[i+1] - c[i]。这意味着在按排序顺序处理对时，我们不再需要检查凸属性。所以步骤#4 的唯一任务是增长子串。

该算法的这种简化变体需要 O(N ² ) 空间。P[]如果我们使用输入数组的预排序副本和S[]优先级队列来代替大型数组，则可以降低空间复杂度。步骤#4 从该优先级队列的顶部接收元素。为了保持优先级队列的大小等于 N，我们可以S[i+1] - S[j]仅在删除元素后将元素推送到队列S[i] - S[j]（因此​​队列只为每个元素保留一个元素j）。如果我们使用已知的 DP 技巧来仅存储一个指向原始后指针链“中间”的后指针（对于每个索引）（然后递归地重复此算法），则不需要后指针森林消耗巨大的空间对于这个“中间”后向指针之前和之后的两个子数组）。

以及 O(N ³ ) 算法：

1. 构造图，其中每个顶点对应于（按索引排序）数组元素对。
2. 如果顶点有一个公共数组元素，该元素位于与这些顶点关联的其余两个元素之间，并且所有三个元素都满足凸属性，则用一条边连接顶点。该边应指向索引较大的顶点。
3. 添加源节点和目标节点并将它们连接到每个顶点。
4. 找出图中最长的路径。

该图有 O(N ² ) 个顶点和 O(N ³ ) 个边。它可以在 O(N ³ ) 时间内构建；由于它是 DAG，因此找到最长路径也需要 O(N ³ ) 时间。