0

块不能重叠。它们也不能相邻。假设 A 的长度 > 2。

我知道这与查找最大子数组的总和非常相似，并且可以在线性时间内完成。

我也很确定该算法的开始与查找最大子数组问题相同。

这是我前几天听到的一个问题，想看看如何解决。

4

2 回答 2

2

你可以做两次 max-subarray-algorithm 。

算法

  1. 我们定义了一个函数 L[i]，它表示 a[i] 之前的 max-subarray 的总和。它可以从左到右执行最大子数组算法，复杂度为 O(n)。
  2. 我们定义了一个函数 R[i]，它表示 a[i] 之后的 max-subarray 的总和。它可以从右到左执行最大子数组算法，复杂度为 O(n)。
  3. 从 1 扫描到 n，答案将是最大的 L[i] + R[i+1]。这一步将是 O(n) 复杂度。
  4. 简单证明：任何解决方案都将从数组中的一个元素中分割出来，因此我们可以计算每个位置前后的 max-subarray 之和。

代码

def max_two_sub_array():
    sum = l[0] = ls[0] = 0
    for i = 1 to n:
        sum += a[i]
        if sum < 0: sum = 0
        if l[i - 1] > sum:
            l[i] = l[i - 1]
            ls[i] = ls[i - 1] # endpoint of l[i]
        else
            l[i] = sum
            ls[i] = i

    sum = r[n + 1] = 0
    rs[n + 1] = n + 1
    for i = n to 1:
        sum += a[i]
        if r[i + 1] > sum:
            r[i] = r[i + 1]
            rs[i] = rs[i + 1] # startpoint of r[i]
        else
            r[i] = sum
            rs[i] = i
    ans = 0
    for i = 0 to n:
        ans = max(ans, l[i] + r[i + 1])
    return ans
于 2013-01-25T03:11:50.840 回答
-1

2个步骤：

  1. 使用 O(n) 找到整个数组中最大和的块。假设块从a[i]开始，以a[j]结束，总和为S1

  2. 使用 O(n) 找到前一个块的和最小的块。假设总和为 S2

最终答案是 S1-S2

应考虑一些边界情况：

如果数组是 1,2,3,2,1。第 1 步将整个数组作为块返回。第 2 步将返回 1。但这违反了 2 个块不应相邻的要求。所以对于第 2 步，你应该应用从 a[i+1] 开始并以 a[j-1] 结束的算法

于 2013-01-25T02:17:16.417 回答