请教碰到的一道算法题，最大和的连续子数组

• 資深大佬 : jmc891205

  最简单的做法就是把动态规划的状态保存下来，找到最大和之后再去回溯就好了。

• 資深大佬 : EthanDon

  算法导论上看过，用分治策略很简单。
  递归将数组拆分为两半，分别计算各自的 ans，记录下标，例如本题中：
  [-2,11,-4,13,-5,-2] -> [-2,11,-4], [13,-5,-2]
  其中[-2,11,-4] -> [-2,11], [-4]
  分别得到 [-2,11], [-4] 的 ans 为[11]和[-4]；进行归并，11 + (-4) < 11 ；所以[-2,11,-4]的 ans 为[11]
  同理计算得到[13,-5,-2]的 ans 为 13
  归并： [-2,11,-4], [13,-5,-2] : 11 + （-4 ）+ 13 =20，20>11 （左子数组），20>13(右子数组）；得到结果[11,-4,13]。

  从贪心的角度可以证明思路正确：将一个数组拆分为两部分，最大连续数组和出现的情况只有三种：左，右，跨左右。其中跨左右的计算方式为左数组加中间部分的数组和右数组。

  年代久远可能记错了，有些地方考虑不够周全。

• 資深大佬 : I2E

  public function getBiggestSubarray($arr, $max, $record = [])
  {
  if (count($arr) <= 1) {
  return $arr[0] > $max ? $arr : $record;
  }

  foreach ($arr as $k => $v) {
  $sum = array_sum(array_slice($arr, $k));
  if ($sum >= $max) {
  $max = $sum;
  $record = array_slice($arr, $k);
  }
  }

  $arr = array_splice($arr, 0, count($arr) – 1);
  return $this->getBiggestSubarray($arr, $max, $record);
  }

• 資深大佬 : I2E

  https://gist.github.com/zhaofenghao/54a6188c1e88c986d7abc8be6b13e17a  显示 Gist 代码