分治算法

核心思想：分解---解决---合并

一次股票买入卖出问题可以转换成寻找最大连续子数组问题。

case1：[1, -2, 3, -4, 5, -6]
case2：[1, 3, -4, -3, 8, -1, -2, -3, 4]
case3：[9, -8, 3, 4, -5, 6]

可用贪心解决，维护最大连续子数组之和（max_sum）和最大的最大连续子数组之和（max_max_sum）的堆。

这篇写分治，用分治解决：

先找出中间位置，最大连续子数组和能落在中间左边，也可能落在中间右边，还可能跨越中间值。

如果落在两边的话，直接从中间扫描过去就好了！！！

如果跨越中间值，从中间往左扫找到左半区间，在从中间往右扫找到右半区间，拼接在一起！完事！！！

下面是 python 代码，写之前先想好输入和输出：

先设计输入和输出：

def findmaxArray(target, low, high):
  # 合并部分
   if low == high:
      return (low, high, target[high])
   # 解决部分
   mid = (low + high) // 2
   leftLow, leftHigh, leftMaxSum = findmaxArray(target, low, mid)
   rightLow, rightHigh, rightMaxSum = findmaxArray(target, mid+1, high)
   corssLow, crossHigh, crossMaxSum = findmaxArrayCrossMid(target, low, mid, high)
   # 合并部分
   if leftMaxSum >= rightMaxSum and leftMaxSum >= crossMaxSum:
      return (leftLow, leftHigh, leftMaxSum)
   elif rightMaxSum >= leftMaxSum and rightMaxSum >= crossMaxSum:
      return (rightLow, rightHigh, rightMaxSum)
   else:
      return (corssLow, crossHigh, crossMaxSum)


def findmaxArrayCrossMid(target, low, mid, high):
   leftSum, rightSum = 0, 0
   leftMaxSum, rightMaxSum = float('-inf'), float('-inf')
   for i in range(mid, low - 1, -1):
      leftSum += target[i]
      if leftSum > leftMaxSum:
         leftMaxSum = leftSum
         crossLow = i
   for i in range(mid+1, high + 1):
      rightSum += target[i]
      if rightSum > rightMaxSum:
         rightMaxSum = rightSum
         crossHigh = i
   return (crossLow, crossHigh, leftMaxSum + rightMaxSum)

if __name__ == '__main__':
   target = [1, -2, 3, -4, 5, -6]
   t = findmaxArray(target, 0, len(target)-1)
   print(t)
   target = [1, 3, -1, -2, 8, -1, -2, -3, 4]
   t = findmaxArray(target, 0, len(target)-1)
   print(t)
   target = [9, -8, 3, 4, -5, 6]
   t = findmaxArray(target, 0, len(target)-1)
   print(t)