顺序递增递减
Sequence increasing and decreasing by turns
假设我们有一个给定长度的整数序列 n。我们要删除一些元素（可能是none），让序列在result中依次递增递减。这意味着，每个元素都应该有比它大或比它小的相邻元素。
例如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) 可能）和正确地解决这个问题吗？
对于索引为 i 的序列中的每个元素，我们将计算 F(i, high) 和 F(i, low)，其中 F(i, high) 等于具有所需特征的子序列的最大总和以第 i 个元素结尾，这个元素是 "high peak"。 （我主要解释"high"部分，"low"部分可以类似的做）。我们可以使用以下关系计算这些函数：
答案是所有 F(i, high) 和 F(i, low) 值中的最大值。
这为我们提供了一个具有 O(n^2) 时间复杂度的相当简单的动态规划解决方案。但我们可以走得更远。
我们可以优化max(F(j,low))部分的计算。我们需要做的是在a[j] < a[i]的条件下，在之前计算的F(j, low)中找到最大值。这可以用 segment trees 来完成。
首先，我们将 "squeeze" 我们的初始序列。只有在求和的时候才需要元素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]段上构建一个线段树，每个节点包含其中的最大和段（相应地，"high" 和 "low" 部分需要两个段树）。现在让我们描述一下算法的步骤i：
- 使用 "low" 线段树（最初树的所有节点都包含零）在线段
[0, b[i]-1] 上找到最大和 max_low。
F(i, high) 等于 max_low + a[i].- 使用 "high" 线段树在线段
[b[i]+1, n] 上找到最大和 max_high。
F(i, low) 等于 max_high + a[i].- 用
F(i, high) 值更新 [b[i], b[i]] 段树的 "high" 段，重新计算父节点（和 [b[i], b[i]] 节点本身）的最大值。
- 对 "low" 段树和
F(i, low) 执行相同的操作。
复杂度分析：b序列计算为O(n*log(n))。线段树 max/update 操作具有 O(log(n)) 的复杂性，其中有 O(n)。该算法的总体复杂度为O(n*log(n))。
假设我们有一个给定长度的整数序列 n。我们要删除一些元素（可能是none），让序列在result中依次递增递减。这意味着，每个元素都应该有比它大或比它小的相邻元素。
例如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) 可能）和正确地解决这个问题吗？
对于索引为 i 的序列中的每个元素，我们将计算 F(i, high) 和 F(i, low)，其中 F(i, high) 等于具有所需特征的子序列的最大总和以第 i 个元素结尾，这个元素是 "high peak"。 （我主要解释"high"部分，"low"部分可以类似的做）。我们可以使用以下关系计算这些函数：
答案是所有 F(i, high) 和 F(i, low) 值中的最大值。
这为我们提供了一个具有 O(n^2) 时间复杂度的相当简单的动态规划解决方案。但我们可以走得更远。
我们可以优化max(F(j,low))部分的计算。我们需要做的是在a[j] < a[i]的条件下，在之前计算的F(j, low)中找到最大值。这可以用 segment trees 来完成。
首先，我们将 "squeeze" 我们的初始序列。只有在求和的时候才需要元素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]段上构建一个线段树，每个节点包含其中的最大和段（相应地，"high" 和 "low" 部分需要两个段树）。现在让我们描述一下算法的步骤i：
- 使用 "low" 线段树（最初树的所有节点都包含零）在线段
[0, b[i]-1]上找到最大和max_low。 F(i, high)等于max_low + a[i].- 使用 "high" 线段树在线段
[b[i]+1, n]上找到最大和max_high。 F(i, low)等于max_high + a[i].- 用
F(i, high)值更新[b[i], b[i]]段树的 "high" 段，重新计算父节点（和[b[i], b[i]]节点本身）的最大值。 - 对 "low" 段树和
F(i, low)执行相同的操作。
复杂度分析：b序列计算为O(n*log(n))。线段树 max/update 操作具有 O(log(n)) 的复杂性，其中有 O(n)。该算法的总体复杂度为O(n*log(n))。