考虑下面这样一个数组：
{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）更及时地解决这个问题？
最佳答案
我相信我有一个在O（N）时间内运行的算法。我将首先描述算法的未优化版本，然后给出一个完全优化的版本。
为了简单起见，我们首先假设原始数组中的所有值都是不同的。总的来说这不是真的，但它提供了一个很好的起点。
算法背后的关键观察如下。找到数组中最小的元素，然后将数组分成三部分：最小值左边的所有元素、最小值元素本身和最小值右边的所有元素。示意图上，这看起来像
+-----------------------+-----+-----------------------+
| left values | min | right values |
+-----------------------+-----+-----------------------+
这里有一个关键的观察：如果你选择给出最佳值的子阵，那么三件事之一必须是真的：
该数组包含数组中的所有值，包括最小值。它的总值是min*n，其中n是元素的数量。
该数组不包含最小元素。在这种情况下，子数组必须完全位于最小值的左侧或右侧，并且不能包含最小值本身。
这为解决此问题提供了一个很好的初始递归算法：
如果序列为空，则答案为0。
如果序列不是空的：
找出序列中的最小值。
返回下列最大值：
子阵列的最佳答案在最小值的左边。
子阵列的最佳答案在最小值的右边。
元素数乘以最小值。
那么这个算法有多有效呢？好吧，那真的取决于最小元素在哪里。如果你考虑一下，我们做线性工作来找到最小值，然后把问题分成两个子问题，并在每个子问题上递归。这与考虑快速排序时得到的结果完全相同。这意味着，在最好的情况下，它需要_（n logn）时间（如果我们总是在每一半的中间有最小元素），但在最坏的情况下，它需要_（n2）时间（如果我们总是在最左边或最右边有最小值）。
但是，请注意，我们花费的所有精力都被用于在每个子阵列中找到最小值，这需要k个元素花费o（k）时间。如果我们能加速到0（1）次呢？在这种情况下，我们的算法将做更少的工作。更具体地说，它只能起到O（N）的作用。原因如下：每次进行递归调用时，我们都执行o（1）操作以找到最小元素，然后从数组中删除该元素并递归处理剩余的部分。因此，每个元素最多可以是一个递归调用的最小元素，因此递归调用的总数不能大于元素的数目。这意味着我们最多只能进行o（n）调用，即每个do o（1）work，这就产生了总共o（1）work。
那么我们到底怎么才能得到这种神奇的加速呢？在这里，我们可以使用一种出人意料的通用性和不受重视的数据结构Cartesian tree。笛卡尔树是由具有以下属性的元素序列创建的二叉树：
每个节点都小于其子节点，并且
笛卡尔树的有序遍历按元素出现的顺序返回序列元素。
例如，序列
4 6 7 1 5 0 2 8 3具有以下笛卡尔树： 0
/ \
1 2
/ \ \
4 5 3
\ /
6 8
\
7
这就是我们得到魔法的地方。我们可以通过查看笛卡尔树的根立即找到序列的最小元素-只需0（1）次。一旦我们这样做了，当我们进行递归调用并查看最小元素左边或右边的所有元素时，我们只是递归地下降到根节点的左边和右边子树中，这意味着我们可以读取这些子数组的最小元素，每次0（1）次。漂亮！
真正的好处是可以在o（n）时间内为n个元素的序列构造笛卡尔树。该算法详细说明了in this section of the Wikipedia article。这意味着我们可以得到一个超快速算法来解决您的原始问题，如下所示：
为数组构造笛卡尔树。
使用上述递归算法，但使用笛卡尔树来查找最小元素，而不是每次都执行线性扫描。
总的来说，这需要o（n）时间并使用o（n）空间，这是对最初的o（n2）算法的时间改进。
在讨论开始时，我假设所有数组元素都是不同的，但这并不是真正必要的。通过将每个节点小于其子节点的要求更改为每个节点不大于其子节点，您仍然可以为其中包含非不同元素的数组构建笛卡尔树。这不会影响算法或其运行时的正确性；我将把它作为众所周知的“练习留给读者”。
这是个很酷的问题！我希望这有帮助！