递归法求解最大连续子序列和MaxSubSum

何为递归呢

• 总结一句话就是：向基准情形不断推进
  核心就在于 “递” 和 “归”
  递：不断推进
  归：向基准情形
• 结合今天的例子进一步解释如下：
  分而治之的思想 divide and conquer
  分三步：“分”“治”“合并”
  “分”：
  将子序列看作三种，左半部分 右半部分 跨越中间元素的子序列
  “治”：
  左右两部分利用递归寻找最大子序列和，跨越中点的最大子序列和(即在左半部分开始，右半部分结束)
  “合并”：
  将得到的三个结果取max就得到了想要的结果

求解最大子序列和

求解一个最大子序列和，有三种情况，在讨论之前我们先规定中间元素简称为mid。这三种情况是：
1、子序列在mid左边
2、子序列在mid右边
3、子序列跨越mid
那么求解子序列和与递归法有什么关系呢
首先我们来看一个图解:

在这个问题中，
基准情形是：
当序列中只有一个元素时，最大子序列和就是它本身
逐渐推进体现在：
数据规模一直在减半，在减半的过程中，序列元素个数不断减少，到最后一层就是基准情形。
综上: 该问题满足像基本情形不断推进，因此可以用该思路写递归算法

出现过的报错:RecursionError: maximum recursion depth exceeded in comparison

写代码小tips

ctrl+r快捷键替换:

![在这里插入图片描述](/i/ll/?i=direct/dbffd746f8e8465d8c99d8043ba9cb7d.png

代码如下

def maxsubsum(nums,left,right):
    #基准情形 序列中只有一个元素，那么它就是最大的
    if left==right:
        return nums[left]
    mid=(left+right)//2#一定要注意这里加法要加括号！！！血泪教训，会陷入死循环
    #递归：分别对左边的序列和右边的序列运行maxsubsum函数，序列中不包含mid对应的元素
    maxleftsum = maxsubsum(nums,left,mid)
    maxrightsum = maxsubsum(nums,mid+1,right)
    #跨越中间元素的子序列和，分别求出左边最大和右边最大，加和即为结果
    left_all_sum=0
    max_left_all_sum=0
    left_index=mid
    while left_index>=left:
        left_all_sum+=nums[left_index]
        if left_all_sum>max_left_all_sum:
            max_left_all_sum =left_all_sum
        left_index-=1

    right_all_sum = 0
    max_right_all_sum = 0
    right_index = mid+1
    while right_index <= right:
        right_all_sum += nums[right_index]
        if right_all_sum > max_right_all_sum:
            max_right_all_sum = right_all_sum
        right_index += 1

    return max(maxleftsum,maxrightsum,max_left_all_sum+max_right_all_sum )

s=[-1,7,8,-4,999]
left=0
right=len(s)-1
print(maxsubsum(s,left,right))

根据给出的例子输出结果如下