Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
问题描述：输入一个整数数组，数组中有正数也有负数，一个或连续的多个整数组成一个子数组，求所有子数组的和的最大值。 求子数组的和的最大值，首先可以求出数组所有子数组的和，再逐一比较可以得到和的最大值。这是最直观易懂的一种解法。但是对一个长度为n的数组，总共有n(n+1)/2个子数组，计算所有子数组的和时间复杂度为O(n^2)。而当n较大时，这种算法是很难被用户接受的。 对于数组(a1, a2, a3, ……, an)，设curSum为当前子数组(ai, ai+1, ……, aj)的和，令k = j + 1且k ≤ n， sum = 0表示初始时子数组和的最大值。
1、如果curSum + ak > sum，那么sum = curSum + ak
2、如果curSum + ak ≤ 0，说明curSum已经是子数组(ai, ai+1, ……, aj, ak) 的和的最大值,那么curSum = ak，sum保持不变，对应的子数组为(ai, ai+1, ……, aj)
以数组{-1, -2, 3, 10, -4, 7, -2, -5}为例，初始时sum =0, i = 0, curSum = 0
1)i = 0 curSum = -1 sum = -1 2)i = 1 curSum = -2 sum = -1 3)i = 3 curSum = 3 sum = 3 4)i = 4 curSum = 13 sum = 13 5)i = 5 curSum = 9 sum = 13 6)i = 6 curSum= 16 sum = 16 7)i = 7 curSum = 11 sum = 16 有了上述思路，不难写出时间复杂度为O(n)的算法。
PHP实现代码如下：
function maxSubArray($arr) { if (count($arr) < 1) return false; $dp = []; $sum = 0; $start = $end = 0; $curSum = $arr[0]; for ($i = 1; $i < count($arr); $i++) { if ($curSum <= 0) { $start = $i; // 记录更新子数组开始位置 $curSum = $arr[$i]; } else { $curSum += $arr[$i]; } if ($curSum > $sum) { $sum = $curSum; $end = $i; // 记录并更新子数组结束位置 } } echo $start.'--'.$end; var_dump(array_slice($arr, $start, $end - $start + 1)); return $sum; } echo maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);