-1

给定一个由 N 个元素组成的数组 A。我们的任务是在恰好应用一次以下操作后找到最大子数组和：

. 选择任何子数组并将其中的所有元素设置为零。

例如：- 数组是 -1 4 -1 2 那么答案是 6，因为我们可以在索引 2 处选择 -1 作为子数组并将其设为 0。因此，在应用操作后，resultatnt 数组将是：-1 4 0 2。最大和子数组为 4+0+2 = 6。

我的方法是找到最小和子数组的开始和结束索引，并将所有元素设为该子数组的 0，然后找到最大和子数组。但这种方法是错误的。

4

1 回答 1

0

开始简单：

首先，让我们从问题的一部分开始：找到最大子数组 sum。
这可以通过动态编程来完成：

a = [1, 2, 3, -2, 1, -6, 3, 2, -4, 1, 2, 3]
a = [-1, -1, 1, 2, 3, 4, -6, 1, 2, 3, 4]

def compute_max_sums(a):
    res = []
    currentSum = 0
    for x in a:
        if currentSum > 0:
            res.append(x + currentSum)
            currentSum += x
        else:
            res.append(x)
            currentSum = x
    return res

res = compute_max_sums(a)
print(res)
print(max(res))

快速解释：我们遍历数组。只要总和是非负的，就值得将整个块附加到下一个数字。如果我们在任何时候跌至零以下，我们将丢弃整个“尾部”序列，因为不再保留它不会有利可图，我们重新开始。最后，我们有一个数组，其中第 j 个元素是子数组的最大和，i:j其中0 <= i <= j。
休息只是在数组中找到最大值的问题。

回到原来的问题

现在我们解决了简化版本，是时候进一步研究了。我们现在可以选择一个要删除的子数组来增加最大和。天真的解决方案是尝试所有可能的子数组并重复上述步骤。不幸的是，这将花费太长时间1。幸运的是，有一种方法可以解决这个问题：我们可以将零点视为两个最大值之间的桥梁。
不过还有一件事需要解决——目前，当我们有第 j 个元素时，我们只知道尾部在它后面的某个位置，所以如果我们要从数组中获取最大和第二大元素，它们可能会发生会重叠，这将是一个问题，因为我们会不止一次地计算一些元素。

重叠的尾巴

如何缓解这种“重叠的尾巴”问题？
解决方案是再次计算所有内容，这次是从头到尾。这给了我们两个数组——一个是第 j 个元素的尾部 i 指向数组的左端（例如 i <=j），另一个则相反。现在，如果我们从第一个数组中取出x并从第二个数组中取出y ，我们知道如果 index(x) < index(y) 那么它们各自的子数组是不重叠的。 我们现在可以继续尝试每个合适的 x, y 对 - 有O(n 2 )
其中。然而，由于我们不需要任何进一步的计算，因为我们已经预先计算了这些值，这是算法的最终复杂性，因为准备工作只花费我们 O(n)，因此它不会施加任何额外的惩罚。

这里是龙

到目前为止，我们所做的事情相当简单。以下部分并不复杂，但会有一些活动部分。是时候刷一下最大堆了：

  • 访问最大值是在恒定时间内
  • 如果我们有对该元素的引用，则删除任何元素都是 O(log(n))。（我们在 O(log(n) 中找不到元素）。但是，如果我们知道它在哪里，我们可以将它与堆的最后一个元素交换，删除它，然后在 O(log (n))。
  • 将任何元素添加到堆中也是 O(log(n))。
  • 构建堆可以在 O(n) 中完成

话虽如此，由于我们需要从头到尾，我们可以构建两个堆，一个用于我们预先计算的数组。我们还需要一个帮助数组，它可以让我们快速索引 -> 堆中元素访问以获取 log(n) 中的删除。

第一个堆将开始为空 - 我们在数组的开头，第二个将开始满 - 我们已经准备好整个数组。

现在我们可以遍历整个数组。在每个步骤中，我们：

  • 将 max(heap1) + max(heap2) 与我们当前的最佳结果进行比较，以获得当前的最大值。O(1)
  • 将第一个数组中的第 i 个元素添加到第一个堆中 - O(log(n))
  • 从第二个堆中删除第 i 个索引元素（这就是我们必须将引用保存在辅助数组中的原因） - O(log(n))

结果复杂度为O(n * log(n))。

更新：

只是一个 O(n 2 ) 解决方案的快速说明，因为 OP 礼貌而礼貌地询问。伙计，伙计，我不是你的兄弟。
注意 1：获得解决方案对您的帮助不如您自己找出解决方案。
注2：以下代码给出正确答案的事实并不能证明其正确性。虽然我相当肯定我的解决方案应该有效，但绝对值得研究它为什么有效（如果有效），而不是查看它的一个示例。

input = [100, -50, -500, 2, 8, 13, -160, 5, -7, 100]
reverse_input = [x for x in reversed(input)]
max_sums = compute_max_sums(input)
rev_max_sums = [x for x in reversed(compute_max_sums(reverse_input))]
print(max_sums)
print(rev_max_sums)
current_max = 0
for i in range(len(max_sums)):
    if i < len(max_sums) - 1:
        for j in range(i + 1, len(rev_max_sums)):
            if max_sums[i] + rev_max_sums[j] > current_max:
                current_max = max_sums[i] + rev_max_sums[j]
                
print(current_max)

1有 n 个可能的开始，n 个可能的结束，我们拥有的代码的复杂度为 O(n)，导致复杂度为 O(n 3 )。不是世界末日，但也不是很好。

于 2021-02-23T10:11:23.033 回答