# 最大连续子数组和

xiaoxiao2021-02-28  10

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.

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