基于分治法求解最大子数组问题及区间定位技术问询

1. 分治算法核心思路（含区间定位） #

分治的核心是将数组拆分为左右两半，最大盈利区间必然属于以下三种情况之一：完全在左半部分、完全在右半部分、横跨左右两半。你已经能拆分到单个元素找到最大值，现在关键是在合并阶段同步记录区间的起止月份，而非仅记录数值。

每个递归调用需返回包含三个信息的结果：

• 子区间的最大盈利总和
• 子区间的起始月份（1-based）
• 子区间的结束月份（1-based）

递归执行细节 #

• 拆分阶段：将数组从中间位置mid拆分为左半A[1..mid]和右半A[mid+1..n]，递归处理左右两部分，得到左半最优结果left_res和右半最优结果right_res。
• 合并阶段：计算横跨左右的最优区间，这是定位跨中间区间的关键：
  1. 从mid向左遍历，找到以mid为右边界的最大盈利子区间，记录其左边界cross_left和累计盈利sum_left。
  2. 从mid+1向右遍历，找到以mid+1为左边界的最大盈利子区间，记录其右边界cross_right和累计盈利sum_right。
  3. 横跨区间的总盈利为sum_left + sum_right，对应区间为[cross_left, cross_right]。
• 结果选择：比较左半最优、右半最优、横跨最优的盈利总和，取最大值对应的区间与数值作为当前递归层的结果返回。

示例验证（以案例(cʹ)为例） #

数组A = [30, -50, 20, -5, 40]，中间位置mid=2：

• 左半[30,-50]的最优区间为[1,1]，盈利30；
• 右半[20,-5,40]的最优区间为[3,5]，盈利55；
• 横跨区间：向左从mid=2遍历仅能取[2,2]（盈利-50），向右从3遍历取[3,5]（盈利55），总盈利为5，远小于右半的55，因此最终返回右半的结果。

2. 算法正确性证明 #

分治算法的正确性基于三种情况完全覆盖了所有可能的最大盈利区间：

1. 最大区间完全在左半：递归处理左半时会找到该区间；
2. 最大区间完全在右半：递归处理右半时会找到该区间；
3. 最大区间横跨左右：通过向左/向右遍历的贪心方式，能找到跨中间点的最大盈利区间——因为从中间向左的最大盈利必然包含中间点，向右同理，两者相加即为跨中间的最优解。

三种情况无遗漏、无重叠，因此最终选出的结果必然是全局最优。

3. 时间复杂度分析与递推关系 #

递推式推导 #

设T(n)为处理长度为n的数组的时间：

• 拆分阶段：将数组拆分为两个长度为n/2的子数组，时间开销为2*T(n/2)；
• 合并阶段：横跨左右的遍历需覆盖整个数组，时间开销为O(n)；
• 基础情况：当n=1时，处理单个元素的时间为O(1)。

因此递推关系为：

T(n) = 2*T(n/2) + O(n)  （n>1）
T(1) = O(1)

递推式求解 #

用主定理求解：主定理形式为T(n) = a*T(n/b) + f(n)，此处a=2，b=2，f(n)=n。
由于n^(log_b a) = n^(log_2 2) = n，与f(n)同阶，因此时间复杂度为O(n log n)。

4. 伪代码实现（带区间记录） #

def max_profit_interval(A, left_idx, right_idx):
    # 基础情况：单个元素（输入索引为0-based，返回月份为1-based）
    if left_idx == right_idx:
        return (A[left_idx], left_idx + 1, right_idx + 1)
    
    mid_idx = (left_idx + right_idx) // 2
    # 递归处理左右子数组
    left_sum, left_start, left_end = max_profit_interval(A, left_idx, mid_idx)
    right_sum, right_start, right_end = max_profit_interval(A, mid_idx + 1, right_idx)
    
    # 计算跨中间点的最大盈利与区间
    # 向左遍历找最大和
    cross_left_sum = -float('inf')
    current_sum = 0
    cross_left_month = mid_idx + 1  # 初始化为中间点的1-based月份
    for i in range(mid_idx, left_idx - 1, -1):
        current_sum += A[i]
        if current_sum > cross_left_sum:
            cross_left_sum = current_sum
            cross_left_month = i + 1  # 转成1-based月份
    
    # 向右遍历找最大和
    cross_right_sum = -float('inf')
    current_sum = 0
    cross_right_month = mid_idx + 1  # 初始化为中间点下一个的1-based月份
    for i in range(mid_idx + 1, right_idx + 1):
        current_sum += A[i]
        if current_sum > cross_right_sum:
            cross_right_sum = current_sum
            cross_right_month = i + 1
    
    cross_total = cross_left_sum + cross_right_sum
    
    # 选择最优结果返回
    max_total = max(left_sum, right_sum, cross_total)
    if max_total == left_sum:
        return (left_sum, left_start, left_end)
    elif max_total == right_sum:
        return (right_sum, right_start, right_end)
    else:
        return (cross_total, cross_left_month, cross_right_month)

调用示例：

A = [30, -50, 20, -5, 40]
total_profit, start_month, end_month = max_profit_interval(A, 0, len(A)-1)
print(f"最大盈利区间为第{start_month}-{end_month}月，盈利{total_profit}")

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