题目描述

给定一个数组 A，找出此数组中，所有子数组中和最大的子数组，即为最大子数组问题。

基本步骤

分解

对原数组进行二分，也就是将数组划分为左右相等（或者相差一个元素）的两个子数组。

合并

对半分的时候需要注意，中间重合部分的。
原数组，左边数组+右边数组+中间 合并而成。
求三个值的最大解即可

max{subLMax,subRMax,subMMax}

横跨在两个子问题上的最大子数组

  • 只要一次遍历左右数组的所有子数组，即可找到横跨在两个子问题上的最大子数组
  • 复杂度