algorithm - 顺序递增递减

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) 或 O(n log n))和正确地解决这个问题吗？

Answer 1

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

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

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

我们可以优化 max(F(j,low)) 的计算部分。我们需要做的是在之前计算的F(j, low)中找到最大值条件是 a[j] < a[i] .这可以通过 segment trees 来完成.

首先，我们将“压缩”我们的初始序列。我们需要元素的实际值 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)) .