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

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

算法导论上看过，用分治策略很简单。
递归将数组拆分为两半，分别计算各自的 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]。

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

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

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);
}