栅栏-波兰信息学奥林匹克运动会的任务

Question

最近，我遇到了波兰信息学奥林匹克运动会的一项名为“栅栏”的任务，但我无法解决。

第一输入行包含整数号n (1 <= n <= 200 000)，第二行包含n数字(每一行不小于1，不大于10^6)。您必须删除一些数字，以便剩余的数字的和尽可能大，它们的值必须增加和减少。我的意思是，如果A是一组剩余的数，而ai是从集到a1 < a2 > a3 < a4 > a5 < a6等的i-th数或a1 > a2 < a3 > a4 < a5 > a6等。

从n值的范围来看，解决方案的复杂性似乎与O(n log n)相似，但我不确定。如果有人告诉我解决方案，我会很感激的。

一些示例

输入：

2 100 90

输出：

一百九十

输入：

6 7 5 4 6 6

输出：

23

Answer 1

谢谢!最后我想出了一个解决方案。

我将创建两个数组(比方说dp_bigger和dp_smaller)，第一个数组用于最大和，结束于第一个元素(当我大于前一个包含元素时)和第二个数组，当第一个元素小于前一个包含元素时。为了计算dp_biggeri，我计算了arri的和，以及以前从dp_smaller在某个索引j (0 <= j< i)处计算出来的最大和。

当然，我必须记住，当我计算dp_biggeri时，我找到了一些最大和的dp_smallerj，我必须检查arri > arrj。对于dp_smaller，我也是这样做的，但是我检查arri < arrj。

现在，如果我想快速找到这些最大值，我将创建另外两个数组(称为大数组和小数组)，每个数组的大小为10^6。当我在更大的[arri-1]中计算一些dp_biggeri时，我将dp_biggeri和dp_smalleri放在相同的位置，这样就可以在数组上创建一个越来越大的范围树。由于这个原因，当我想要计算dp_biggeri时，我在数组中搜索最大值，从0到arri-2的范围更小，如果我想计算dp_smaller，在arri上搜索到10^6。

我认为这是正确的解决方案，再次感谢这些暗示。