You need to enable JavaScript to run this app. 如何编写递归程序求解数组中最大前缀和对应的索引
优惠活动
大模型
产品
解决方案
定价
更多

如何编写递归程序求解数组中最大前缀和对应的索引

递归实现最大前缀和对应索引的方案

需求逻辑对齐

先预计算题目给出的示例的前缀和序列,确认计算规则无偏差:

  • 数组[1,-5,9,-12,3,3,3,2]的前缀和序列为[1, -4, 5, -7, -4, -1, 2, 4],最大值为5,对应索引2,与示例匹配
  • 数组[1,-5,9,7]的前缀和序列为[1, -4, 5, 12],最大值为12,对应索引3,与示例匹配

递归实现思路

递归执行过程无需重复累加计算前缀和,仅需在递归栈中维护三组动态跟踪的状态值,避免冗余运算:

  1. 当前遍历到的数组下标
  2. 截至当前下标的累计前缀和
  3. 历史遍历过程中记录的最大前缀和、以及对应的索引值

递归执行规则

  • 终止条件:当前下标等于数组长度时,代表所有元素遍历完成,直接返回记录的最大前缀和对应索引
  • 单步处理逻辑:
    • 将当前下标的元素值累加到累计前缀和上
    • 对比当前累计前缀和与历史最大值:如果当前值更大,就同步更新历史最大值和对应的索引位置
    • 带着更新后的状态,递归处理数组的下一个下标

递归代码实现

def find_max_prefix_index(arr, current_idx=0, current_sum=0, max_sum=-float('inf'), max_idx=0):
    # 遍历到数组末尾,返回记录的最大索引
    if current_idx == len(arr):
        return max_idx
    # 计算当前位置的累计前缀和
    current_sum += arr[current_idx]
    # 更新最大值与对应索引
    if current_sum > max_sum:
        max_sum = current_sum
        max_idx = current_idx
    # 递归处理下一个元素
    return find_max_prefix_index(arr, current_idx + 1, current_sum, max_sum, max_idx)

效果验证

  • 执行find_max_prefix_index([1,-5,9,-12,3,3,3,2]),返回值为2,匹配示例结果
  • 执行find_max_prefix_index([1,-5,9,7]),返回值为3,匹配示例结果

边界场景注意事项

  • 注意:初始最大和值设为负无穷,规避数组全为负数时的判断错误:比如数组[-3,-1,-2]的前缀和为[-3, -4, -6],最大前缀和为索引0处的-3,如果初始值设为0会返回错误结果
  • 如果需求调整为“多个位置的前缀和相等且为最大值时,返回最后一次出现的索引”,仅需将判断条件中的current_sum > max_sum修改为current_sum >= max_sum即可

内容的提问来源于stack exchange,提问作者Mathlover1996

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.02 08:45:04