求解整数数组中两个不相交子数组的最大和

原有思路的缺陷 #

你这个思路无法得到全局最优结果，核心问题是默认两个选中的子数组必须包含全局最大和子数组，但实际存在两个子数组的和均小于全局最大子数组、但二者加和更大的场景。
举个明确的反例：对于数组[5, -2, 3, -2, 5]，全局最大子数组为整个数组，和为9。按照你的思路，该子数组覆盖了全部下标，切分后左右区间均为空，计算得到的结果为9，但实际最优解是选取左侧的5，和右侧[3,-2,5]段（和为6），总加和为11，明显优于你思路得到的结果。

可行解题方案 #

核心逻辑 #

两个互不相交的连续子数组，必然存在一个分割点将原数组拆分为左右两个独立区间，两个子数组分别落在左右区间内。我们只需要枚举所有可能的分割点，计算每个分割点下「左区间最大子数组和 + 右区间最大子数组和」，所有结果中的最大值就是答案。

具体步骤 #

• 预处理左前缀最大数组left_max：从左向右遍历数组，left_max[i]代表下标0到i区间内可选取的最大子数组和。题目允许子数组为空，因此如果区间内全为负数，直接取空数组和0即可，用改造后的Kadane算法计算。
• 预处理右后缀最大数组right_max：从右向左遍历数组，right_max[i]代表下标i到数组末尾区间内可选取的最大子数组和，计算逻辑和左数组一致。
• 枚举所有分割位置：分割点位于k和k+1之间（k的取值范围为-1到数组长度减1，k=-1代表左区间为空，k=数组长度减1代表右区间为空），计算对应左右区间的最大和相加，记录全局最大值即为最终结果。

复杂度 #

• 时间复杂度：O(n)，全程仅需三次线性遍历，无嵌套循环。
• 空间复杂度：O(n)，需要存储两个长度为n的预处理数组，常规数据规模下完全够用；如果有极致空间要求，可优化到O(1)，但会牺牲代码可读性。

代码实现（Python） #

def max_two_non_overlapping_subarray(nums):
    n = len(nums)
    if n == 0:
        return 0
    left_max = [0] * n
    # 计算左前缀最大和
    cur_sum = 0
    cur_max = 0
    for i in range(n):
        cur_sum = max(0, cur_sum + nums[i])
        cur_max = max(cur_max, cur_sum)
        left_max[i] = cur_max
    # 计算右后缀最大和
    right_max = [0] * n
    cur_sum = 0
    cur_max = 0
    for i in range(n-1, -1, -1):
        cur_sum = max(0, cur_sum + nums[i])
        cur_max = max(cur_max, cur_sum)
        right_max[i] = cur_max
    # 枚举所有分割点求最大值
    res = 0
    for k in range(-1, n):
        left_val = left_max[k] if k >= 0 else 0
        right_val = right_max[k+1] if k + 1 < n else 0
        res = max(res, left_val + right_val)
    return res

你可以用之前的反例测试：传入[5,-2,3,-2,5]返回11，传入全负数组[-1,-2,-3]返回0（选两个空数组），传入[4,-5,4]返回8，结果均符合预期。

内容的提问来源于stack exchange，提问作者pensee