修复Python中计算两段连续非空收款序列最大利润和的Bug

需求说明 #

需要计算单日营业时间内两段连续非空收款序列（含退款，以实数序列表示）的最大总和，无需定位具体时段：

• 示例1输入：1 2 3 -1 1 2 3，预期结果12（两段分别为1+2+3和1+2+3，总和6+6=12）
• 示例2输入：1 2 1 2 1，预期结果7（两段分别为1+2+1和2+1，总和4+3=7）

原代码问题分析 #

原代码实现的是单段最大子数组和的Kadane算法，只能找出一段连续序列的最大利润：

checks = list(map(float, input().split()))
max_profit = float('-inf')
current_profit = 0
for check in checks:
    current_profit += check
    max_profit = max(max_profit, current_profit)
    if current_profit < 0:
        current_profit = 0
print(max_profit)

对于示例1，单段最大是1+2+3-1+1+2+3=11，所以输出11，不符合两段总和的需求；示例2刚好单段最大（7）和两段总和的预期一致，所以输出正常。

修复后的代码 #

我们需要分别计算每个位置左侧的最大子数组和、右侧的最大子数组和，再遍历所有分割点求两段总和的最大值：

checks = list(map(float, input().split()))
n = len(checks)
if n < 2:
    # 至少需要两个元素才能分成两段非空序列
    print(sum(checks) if n == 1 else 0)
else:
    # 计算左侧最大子数组和数组
    left_max = [0] * n
    current = checks[0]
    left_max[0] = current
    for i in range(1, n):
        current = max(checks[i], current + checks[i])
        left_max[i] = max(left_max[i-1], current)
    
    # 计算右侧最大子数组和数组
    right_max = [0] * n
    current = checks[-1]
    right_max[-1] = current
    for i in range(n-2, -1, -1):
        current = max(checks[i], current + checks[i])
        right_max[i] = max(right_max[i+1], current)
    
    # 遍历所有分割点，求两段总和的最大值
    max_total = float('-inf')
    for j in range(n-1):
        max_total = max(max_total, left_max[j] + right_max[j+1])
    
    print(max_total)

验证结果 #

• 输入1 2 3 -1 1 2 3，输出12，符合预期
• 输入1 2 1 2 1，输出7，符合预期

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