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

Question

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

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

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

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

score 8 · Accepted Answer

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

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

该算法背后的关键观察如下。找到数组中的最小元素，然后将数组拆分为三部分 - 最小值左侧的所有元素、最小值元素本身以及最小值右侧的所有元素。从示意图上看，这看起来像

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

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

该数组由数组中的所有值组成，包括最小值。这具有总值 min * n，其中 n 是元素的数量。
该数组不包括最小元素。在这种情况下，子数组必须完全位于最小值的左侧或右侧，并且不能包含最小值本身。

这给出了一个很好的初始递归算法来解决这个问题：

如果序列为空，则答案为 0。
如果序列非空：
- 找出序列中的最小值。
- 返回以下的最大值：
  - 最小值左侧子数组的最佳答案。
  - 最小值右侧的子数组的最佳答案。
  - 元素数乘以最小值。

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

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

那么我们究竟如何获得这种神奇的加速呢？在这里，我们可以使用一种被称为笛卡尔树的令人惊讶的通用且未被充分认识的数据结构。笛卡尔树是由具有以下属性的元素序列创建的二叉树：

每个节点都小于其子节点，并且
笛卡尔树的中序游走按照它们出现的顺序返回序列中的元素。

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

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

真正的美妙之处在于，可以在 O(n) 时间内为 n 个元素的序列构造一棵笛卡尔树。该算法在 Wikipedia 文章的这一部分中有详细说明。这意味着我们可以获得一个超快速的算法来解决您的原始问题，如下所示：

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

总体而言，这需要 O(n) 时间并使用 O(n) 空间，这是对您最初使用的 O(n ² ) 算法的时间改进。

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

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

score 3 · Accepted Answer

假设这些数字都是非负数，这不就是“最大化直方图中的矩形区域”的问题吗？现在已经成名了……

O(n) 解是可能的。这个网站： http: //blog.csdn.net/arbuckle/article/details/710988有一堆简洁的解决方案。

为了详细说明我的想法（可能不正确），请将每个数字视为宽度为 1 的直方图矩形。

通过“最小化”一个子数组 [i,j] 并加起来，您基本上得到了直方图中从 i 到 j 的矩形区域。

这之前出现在 SO：Maximize the rectangle area under Histogram，你可以找到代码和解释，以及官方解决方案页面的链接（http://www.informatik.uni-ulm.de/acm/Locals/2003/html /judge.html )。

score 0 · Accepted Answer

我尝试的以下算法将具有最初用于对数组进行排序的算法的顺序。例如，如果初始数组使用二叉树排序，则最佳情况为 O(n)，平均情况为 O(n log n)。

算法要点：

数组已排序。存储排序后的值和相应的旧索引。从相应的旧索引创建二叉搜索树，该索引用于确定它可以向前和向后移动多远而不会遇到小于当前值的值，这将导致最大可能的子数组。

我将在问题 [1, 5, 3, 5, 4, 1] 中解释使用数组的方法

                      1  5  3  5  4  1
                  -------------------------
 array indices =>     0  1  2  3  4  5  
                  -------------------------

该数组已排序。按升序存储值及其索引，如下所示

                                   1  1  3  4  5  5
                                 -------------------------
 original array indices =>         0  5  2  4  1  3  
 (referred as old_index)         -------------------------

参考价值及其旧指数很重要；像一个关联数组；

需要明确的几个术语：

old_index 指的是一个元素对应的原始索引（即原始数组中的索引）；

例如，对于元素 4，old_index 为 4；current_index 为 3；

而 current_index 指的是排序数组中元素的索引；current_array_value 指的是排序数组中的当前元素值。

pre 指的是有序的前身；succ 指的是顺序后继者

另外，最小值和最大值可以直接从排序后的数组的第一个和最后一个元素中获取，分别是 min_value 和 max_value；

现在，算法如下，应该在排序数组上执行。

算法：

从最左边的元素开始。

对于排序数组左侧的每个元素，应用此算法

    if(element == min_value){

    max_sum = element * array_length;

        if(max_sum > current_max)
        current_max = max_sum;

        push current index into the BST;

    }else if(element == max_value){

        //here current index is the index in the sorted array
        max_sum = element * (array_length - current_index);

        if(max_sum > current_max)
        current_max = max_sum;


        push current index into the BST;

    }else {

        //pseudo code steps to determine maximum possible sub array with the current element 

        //pre is inorder predecessor and succ is inorder successor

        get the inorder predecessor and successor from the BST;



        if(pre == NULL){

            max_sum = succ * current_array_value;


            if(max_sum > current_max)
            current_max = max_sum;


        }else if (succ == NULL){

            max_sum = (array_length - pre) - 1) * current_array_value;

            if(max_sum > current_max)
            current_sum = max_sum;

        }else {

        //find the maximum possible sub array streak from the values

        max_sum = [((succ - old_index) - 1) + ((old_index - pre) - 1) + 1] * current_array_value;

            if(max_sum > current_max)
            current_max = max_sum;

        } 

    }

例如，

原始数组是

                      1  5  3  5  4  1
                  -------------------------
 array indices =>     0  1  2  3  4  5  
                  -------------------------

排序后的数组是

                                   1  1  3  4  5  5
                                 -------------------------
 original array indices =>         0  5  2  4  1  3  
 (referred as old_index)         -------------------------

在第一个元素之后：

max_sum = 6 [会减少到 1*6]

在第二个元素之后：

max_sum = 6 [会减少到 1*6]

        0
         \
          5

第三个元素之后：

中序遍历结果：0 2 5

应用算法，

max_sum = [((succ - old_index) - 1) + ((old_index - pre) - 1) + 1] * current_array_value;

max_sum = [((5-2)-1) + ((2-0)-1) + 1] * 3 = 12

current_max = 12 [最大可能值]

在第四个元素之后：

中序遍历结果：0 2 4 5

应用算法，

max_sum = 8 [小于 12 被丢弃]

在第五个元素之后：

max_sum = 10 [减少到 2 * 5，因为小于 8 而被丢弃]

在最后一个元素之后：

max_sum = 5 [减少到 1 * 5，因为小于 8 被丢弃]

该算法将具有最初用于对数组进行排序的算法的顺序。例如，如果初始数组使用二元排序进行排序，则最佳情况为 O(n)，平均情况为 O(n log n)。

空间复杂度将为 O(3n) [O(n + n + n)，n 用于排序值，另一个 n 用于旧索引，另一个 n 用于构造 BST]。但是，我不确定这一点。感谢您对算法的任何反馈。

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

3 回答 3

Related

Reference