数组中的最长凸子序列

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. 零-初始化以索引0结尾的子序列长度的数组L[]。n-1.
P[]中的每个对的
4. （按排序顺序）:L[X2]=max(L[X2],L[X1]+1)。其中x是输入数组中元素的索引。
5. 在L[]中查找最大值。这是最长凸子序列的长度。
6. 为了能够重建子序列本身，步骤#4还应该更新后指针链。更新L[X2]时，我们将创建一个节点，指向对应于X1的条目所指向的节点，然后将对应于X2的条目指向此新节点:bp_head[X2]=新节点(bp_head[X1])。

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

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

和O(n3)算法：

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

该图有O(n2)个顶点和O(n3)条边。它可以在O(n3)时间内构造；而且由于它是DAG，寻找最长路径也需要O(n3)的时间。