最大子数组之和

问题：

输入一个整型数组，数据元素有正数也有负数，求元素组合成连续子数组之和最大的子数组。

描述：

输入的数组为1, -2, 3, 10, -4, 7, 2, -5，最大和的连续子数组为3, 10, -4, 7, 2，其最大和为18。

解法：

第一种

最简单，最暴力，最容易理解的一种方法。这种解法的思想就是，从第一个元素开始，然后和后面的所有元素组合求出最大值。
代码：

<?php
class Algorithm
{
  /*
   * 简单暴力法求最大子数组的和
   */
  public function totalOfMaxSubArrayWithSimple(array $array)
  {

      $sum = 0;
      for ($i = 0; $i < count($array); $i++) {
          $tmpSum = $array[$i];
          for ($j = $i + 1; $j < count($array); $j++) {
              $tmpSum += $array[$j];
              if ($tmpSum > $sum) {
                  $sum = $tmpSum;
              }
          }
      }
      return $sum;
  }

这种算法的时间复杂度为O(n^2)。方法简单但是效率低下，一般不采用。

第二种

计算机领域经常使用的一种求解思想，二分查找法，一半一半得淘汰，这样效率会提高很多。这个问题同样也可以用这种思路来解。假设要寻找数组A[low .. high]的最大子数组，使用二分法将A划分为两个等规模子数组。先找到数组A的中央位置 mid，然后分解成两个子数组A[low .. mid]和A[mid+1 .. high]。这样如果存在一个最大的子元素系列A[i .. j]那么它一定满足下面三种情况之一
完全在A[low .. mid]之中
完全在A[mid+1 .. high]
在A[low .. mid]与A[mid+1 .. high]组合的数组中
代码：

<?php

class Algorithm
{
    /*
     * 二分法求最大子数组的和
     */

    public function totalOfMaxSubArray(array $array)
    {
        $left = 0;
        $right = count($array) - 1;
        $mid = floor(($left + $right) / 2);
        if ($left == $right) {
            return $array[$left];
        }
        $leftMax = $this->totalOfMaxSubArray(array_slice($array, $left, $mid - $left + 1));
        $rightMax = $this->totalOfMaxSubArray(array_slice($array, $mid + 1, $right - $mid));
        $midMax = $this->totalOfMaxCrossing($array);
        if ($leftMax > $rightMax && $leftMax > $midMax) {
            return $leftMax;
        } else if ($rightMax > $midMax && $rightMax > $leftMax) {
            return $rightMax;
        } else {
            return $midMax;
        }
    }

    public function totalOfMaxCrossing(array $array)
    {
        $leftTotalMax = PHP_INT_MIN;
        $rightTotalMax = PHP_INT_MIN;

        $left = 0;
        $right = count($array) - 1;
        $mid = floor(($left + $right) / 2);

        $i = $mid;
        $temp = 0;
        while ($i >= $left) {
            $temp += $array[$i];
            if ($temp > $leftTotalMax) {
                $leftTotalMax = $temp;
            }
            $i--;
        }

        $i = $mid + 1;
        $temp = 0;
        while ($i <= $right) {
            $temp += $array[$i];
            if ($temp > $rightTotalMax) {
                $rightTotalMax = $temp;
            }
            $i++;
        }
        return $leftTotalMax + $rightTotalMax;
    }

}


$algorithm = new Algorithm();

($array = range(-11500, 11500)) && shuffle($array);

echo $algorithm->totalOfMaxSubArrayWithSimple($array)."\n";//time：33.592054 s
echo $algorithm->totalOfMaxSubArray($array, 0, 10) . "\n";//time：0.189321 s