algorithm - 找到 2 个具有最大总和的连续数组 block 。归还他们的总和

Question

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

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

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

这是我前两天听到的一个问题，想看看怎么解决。

Answer 1

你可以只执行两次最大子数组算法。

算法

1. 我们定义了一个函数L[i]，表示a[i]之前的最大子数组的和。它可以从左到右执行最大子数组算法O(n) 复杂度。
2. 我们定义了一个函数R[i]，表示a[i]之后的最大子数组的和。它可以从右到左执行最大子数组算法 O(n) 复杂度。
3. 从1扫描到n，答案会是最大的L[i] + R[i+1]。这一步的复杂度为 O(n)。
4. 简单证明:任何解决方案都可以从数组，所以我们可以只计算之前和之前的最大子数组的总和在每个地方之后。

代码

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