按给定1索引伪代码实现，递归最大子数组算法输出错误求修正

需求是从数组中找到「较大数字出现在较小数字之后」的最大差值。例如给定数组 [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]，预期输出为 (7, 11, 43)：其中7是起始索引（对应值63），11是结束索引（对应值106），43是两者的差值（即交易利润）。

但实际运行代码得到的输出是 (0, 16, 1607)。已经查阅过同类问题的讨论帖，但由于需要严格按照提供的伪代码实现，没有找到匹配的参考方案。

import math

def find_max_crossing_subarray(A, low, mid, high):
    max_left = low
    max_right = high
    left_sum = -math.inf
    sum = 0
    for i in reversed(range(low, mid)):
        sum = sum + A[i]
        if sum > left_sum:
            left_sum = sum
            max_left = i

    right_sum = -math.inf
    sum = 0
    for j in range(mid, high):
        sum = sum + A[j]
        if sum > right_sum:
            right_sum = sum
            max_right = j
    return (max_left, max_right, left_sum + right_sum)


def find_maximum_subarray(A, low, high):
    if low + 1 == high:
        return (low, high, A[low])
    else:
        mid = (low + high) // 2
        (left_low, left_high, left_sum) = find_maximum_subarray(A, low, mid)
        (right_low, right_high, right_sum) = find_maximum_subarray(A, mid, high)
        (cross_low, cross_high, cross_sum) = find_max_crossing_subarray(A, low, mid, high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return (left_low, left_high, left_sum)
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return (right_low, right_high, right_sum)
        else:
            return (cross_low, cross_high, cross_sum)

array = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
bf = find_maximum_subarray(array, 0, len(array))
print(bf)

• 当前代码实现的是最大连续子数组求和逻辑，但直接把原始价格数组传入分治函数，完全偏离了最大利润问题的核心计算逻辑。
• 输出的 (0, 16, 1607) 本质是整个原始数组所有元素的累加和：把给定测试数组的所有值加总，结果刚好是1607，覆盖了从索引0到16的全数组区间，和“低买高卖算差值”的需求毫无关系。
• 最大利润问题的分治实现，必须基于原数组的一阶差分数组开展：差分数组的第i个元素等于原数组[i+1] - 原数组[i]，代表相邻位置的价格涨跌幅度。差分数组的最大连续子数组和，才对应原数组里某段的最大价格涨幅，也就是要找的最大利润。

1. 预处理构造差分数组
   不要直接传入原始价格数组，先生成差分数组：
   diff = [array[i+1] - array[i] for i in range(len(array)-1)]
2. 索引映射适配
   分治函数运行在差分数组上，得到差分数组的最大连续子数组的起止索引后，需要映射回原始数组的索引：
   • 买入起始索引 = 差分数组的子数组起始索引（因为差分数组第0位对应原数组0到1的涨幅，买入点就是0）
   • 卖出结束索引 = 差分数组的子数组结束索引 + 1（差分数组第i位的涨幅最终对应原数组i+1位置的卖出价）
3. 调整调用逻辑
   把分治函数的入参换成生成的差分数组，再对返回的结果做索引映射，就能得到符合预期的输出。按照这个逻辑，测试数组上差分数组里的最大连续和刚好是43，对应买入索引7、卖出索引11，和预期完全匹配。

内容的提问来源于stack exchange，提问作者Luka Jozić