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

[guanhui07]

给定一个整数数组 nums [-2,11,-4,13,-5,-2] ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和的连续子数组。

比如 [-2,11,-4,13,-5,-2] 返回 [11,-4,13] ,因为它和最大 是 20

注意：返回的是 子数组 而不是 最大和 整数。

改自 maxinum_subarray

要得到 起始坐标然后再切片做？ 参考

[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