分治算法/最大子列和问题
- 源自数据结构与算法分析
- 基准
- 递归
- 回归操作
- 与递归对应的返回值
- 分解
- 求解
- 合并
- 分解在==递归操作==中
- 将一串序列分为左、右两部分序列
- 求解在==回归操作==中
- 对应的就是先分解，再求解
- 在到达基准（Right==left)，进行回归（求解）
- 在被分为一个元素时，如果元素小于0，那么他就没必要返回了，返回只会减小
- 大于0时，最大子列就是本身
- 对于左侧，从最右边往左加，求最大
- 对于右侧，从最左边往右加，求最大
- 求和
- 利用返回值，保存目前的左侧最大，右侧最大，跨左右最大
- 由于<0的返回值为0
- 每次的左侧右侧最大值在上一次的左侧，右侧，或跨两侧中取最大得
- 左侧右侧应该跨两侧的不足
- 关于递归，因采用数学==归纳法==得，也可以说是验证
- 假设此序列有2个数，例{1,-1}，左=1，右=0，跨=0，最大=1
- 假设有2n个数，成立，最大序列为k，（0，n)， (n+1,2n-1)，后部分可分为（n+1，（3/2）n）与（（3/2）n，2n-1）
- 对于2n+1个，第一次（0，n），（n+1，2n）.其中前一部分可求（由假设得），后部分可分为，（n+1，（3/2）n）与（（3/2）n）
- 经过无限拆分下去，2n+1的右侧始终比2n的右侧多一个1，如果那1个元素是>0,我们带上那个元素，如果那1个元素是<0,我们不带那个元素，即让他=0