arrays - 最大化所有可能子数组的特定总和

Question

考虑一个像下面这样的数组:

  {1, 5, 3, 5, 4, 1}

当我们选择一个子数组时，我们将它减少到子数组中的最小数。例如，子数组 {5, 3, 5}变成 {3, 3, 3} .现在，子数组的和被定义为结果子数组的和。例如， {5, 3, 5}总和是 3 + 3 + 3 = 9 .任务是找到可以从任何子数组中得出的最大可能和。对于上述数组，最大和为 12，由子数组 {5, 3, 5, 4} 给出.

是否有可能比 O(n2) 更好地及时解决这个问题？

Answer 1

我相信我有一个在 O(n) 时间内运行的算法。我将首先描述算法的一个未优化版本，然后给出一个完全优化的版本。

为简单起见，我们最初假设原始数组中的所有值都是不同的。这通常不是真的，但它提供了一个很好的起点。

该算法背后的关键观察如下。找出数组中最小的元素，然后将数组分成三部分——最小值左边的所有元素、最小值元素本身以及最小值右边的所有元素。从原理上讲，这看起来像

 +-----------------------+-----+-----------------------+
 |     left values       | min |      right values     |
 +-----------------------+-----+-----------------------+     

这是关键观察:如果您采用给出最佳值的子数组，则必须满足以下三件事之一:

该数组由数组中的所有值组成，包括最小值。这具有总值 min * n，其中 n 是元素的数量。

该数组不包括最小元素。在这种情况下，子数组必须完全位于最小值的左侧或右侧，并且不能包含最小值本身。

这提供了一个很好的初始递归算法来解决这个问题:

如果序列为空，则答案为 0。

如果序列非空:

找出序列中的最小值。

返回以下最大值:

最小值左侧的子数组的最佳答案。

最小值右侧的子数组的最佳答案。

元素数乘以最小值。

那么这个算法的效率如何呢？嗯，这真的取决于最小元素在哪里。如果你考虑一下，我们会做线性工作来找到最小值，然后将问题分成两个子问题并在每个子问题上递归。这与您在考虑快速排序时得到的重复完全相同。这意味着在最好的情况下它将花费 Θ(n log n) 时间(如果我们总是在每一半的中间有最小的元素)，但在最坏的情况下它将花费 Θ(n2) 时间(如果我们总是在最左边或最右边有最小值。

但是请注意，我们花费的所有精力都用于在每个子数组中找到最小值，这对于 k 个元素需要 O(k) 时间。如果我们可以将其加速到 O(1) 时间会怎样？在这种情况下，我们的算法会做更少的工作。更具体地说，它只会做 O(n) 的工作。原因如下:每次我们进行递归调用时，我们都会做 O(1) 的工作来找到最小元素，然后从数组中删除该元素并递归处理剩余的部分。因此，每个元素可以是最多一个递归调用的最小元素，因此递归调用的总数不能大于元素的数量。这意味着我们最多进行 O(n) 次调用，每个调用都执行 O(1) 工作，总共进行 O(1) 工作。

那么我们究竟如何获得这种神奇的加速呢？在这里，我们可以使用一种名为 的令人惊讶的多功能且未被重视的数据结构。 Cartesian tree .笛卡尔树是由具有以下属性的元素序列创建的二叉树:

每个节点都小于其子节点，并且

笛卡尔树的中序遍历按元素出现的顺序返回序列中的元素。

例如，序列 4 6 7 1 5 0 2 8 3有这个笛卡尔树:

       0
      / \
     1   2
    / \   \
   4   5   3
    \     /
     6   8
      \
       7

这就是我们获得魔法的地方。我们可以通过查看笛卡尔树的根来立即找到序列的最小元素——只需要 O(1) 时间。一旦我们这样做了，当我们进行递归调用并查看最小元素左侧或右侧的所有元素时，我们只是递归地下降到根节点的左右子树，即意味着我们可以在 O(1) 时间内读取这些子数组的最小元素。漂亮!

真正的美妙之处在于，可以在 O(n) 时间内为 n 个元素的序列构造一棵笛卡尔树。此算法详 in this section of the Wikipedia article .这意味着我们可以得到一个超快速的算法来解决你的原始问题，如下所示:

为数组构造一个笛卡尔树。

使用上面的递归算法，但是使用笛卡尔树来寻找最小元素而不是每次都做线性扫描。

总的来说，这需要 O(n) 时间并使用 O(n) 空间，这是对您最初使用的 O(n2) 算法的时间改进。

在本次讨论开始时，我假设所有数组元素都是不同的，但这并不是必需的。您仍然可以通过将每个节点小于其子节点的要求更改为每个节点不大于其子​​节点，为其中包含非不同元素的数组构建笛卡尔树。这不会影响算法的正确性或其运行时间；我将把它作为众所周知的“读者练习”。 :-)

这是一个很酷的问题!我希望这有帮助!