如何编写递归程序求解数组中最大前缀和对应的索引
递归实现最大前缀和对应索引的方案
需求逻辑对齐
先预计算题目给出的示例的前缀和序列,确认计算规则无偏差:
- 数组
[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,与示例匹配
递归实现思路
递归执行过程无需重复累加计算前缀和,仅需在递归栈中维护三组动态跟踪的状态值,避免冗余运算:
- 当前遍历到的数组下标
- 截至当前下标的累计前缀和
- 历史遍历过程中记录的最大前缀和、以及对应的索引值
递归执行规则
- 终止条件:当前下标等于数组长度时,代表所有元素遍历完成,直接返回记录的最大前缀和对应索引
- 单步处理逻辑:
- 将当前下标的元素值累加到累计前缀和上
- 对比当前累计前缀和与历史最大值:如果当前值更大,就同步更新历史最大值和对应的索引位置
- 带着更新后的状态,递归处理数组的下一个下标
递归代码实现
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
相关产品推荐
相关产品推荐

