顺序递增和递减

Question

假设我们有一个给定长度的整数序列n.我们想要删除一些元素(可能没有),以便序列在结果中轮流增加和减少.这意味着,每个元素都应该具有相邻元素,既可以更大,也可以比自身小.例如1 3 2 7 6,5 1 4 2 10两个序列都是轮流增加和减少的.我们想要删除一些元素来转换我们的序列,但我们也希望最大化剩余元素的总和.因此,例如,从序列中2 18 6 7 8 2 10我们想要删除6并制作它2 18 7 8 2 10.

我正在寻找一个有效的解决方案来解决这个问题.上面的例子表明,最天真的贪婪算法(删除每个破坏序列的第一个元素)将不起作用 - 它将删除7而不是6,这将不会最大化剩余元素的总和.任何想法如何有效(O(n) or O(n log n)可能)和正确解决？

Answer 1

对于带有索引的序列中的每个元素，i我们将计算F(i, high)和F(i, low)，其中F(i, high)等于以第 -th 元素结尾的具有所需特征的子序列的最大总和i，并且该元素是“高峰”。（我将主要解释“高”部分，“低”部分可以类似地完成）。我们可以使用以下关系来计算这些函数：

答案是所有F(i, high)和F(i, low)值中最大的。

这为我们提供了一个相当简单且具有时间复杂度的动态规划解决方案O(n^2)。但我们可以走得更远。

我们可以优化零件的计算max(F(j,low))。我们需要做的是找到先前计算的最大值，F(j, low)条件是a[j] < a[i]。这可以通过线段树来完成。

首先，我们将“压缩”我们的初始序列。a[i]仅在计算总和时我们才需要元素的实际值。a[j]但当检查小于时，我们只需要元素的相对顺序a[i]。因此，我们将每个元素映射到排序元素数组中的索引，不重复。例如，序列a = 2 18 6 7 8 2 10将被转换为b = 0 5 1 2 3 0 4. 这可以在 中完成O(n*log(n))。

的最大元素b将小于n，因此，我们可以在该线段上构建一棵线段树，[0, n]其中每个节点都包含线段内最大的和（相应地，我们需要两棵线段树用于“高”和“低”部分）。i现在我们来描述一下算法的步骤：

1. max_low使用“低”线段树找到线段上的最大和[0, b[i]-1]（最初树的所有节点都包含零）。
2. F(i, high)等于max_low + a[i].
3. 使用“高”线段树查找max_high线段上的最大和。[b[i]+1, n]
4. F(i, low)等于max_high + a[i].
5. 使用重新计算父节点（和节点本身）的最大值的值更新[b[i], b[i]]“高”线段树的线段。F(i, high)[b[i], b[i]]
6. 对“低”线段树 和 执行相同的操作F(i, low)。

复杂度分析：b序列计算为O(n*log(n))。线段树最大/更新操作很O(log(n))复杂，而且有O(n)很多。该算法的总体复杂度为O(n*log(n))。