题干
输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个正数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
解题思路
思路一
从头到尾逐个累加数字，初始化和为0，当和为负数时丢弃和，使用下一个数字赋值，和为正数时继续累加，每次累加都与最大值进行比较，如果大于最大值，则替换，直到遍历完后，得到连续累加和的最大值。
思路二
使用动态规划的思想进行分析，f(i) = pData[i] if i=0 or f(i-1) <=0 else f(i-1)+pData[i] if i!=0 and f(i-1)>0
代码实现
思路一
<?php
/**
* 顺序累加的方式求最大和
*/
/**
* @param $numbers
*/
function getGreatestSumOfSubArray($numbers)
{
if (empty($numbers)) {
return;
}
$sum = 0;
$max = PHP_INT_MIN;
$len = count($numbers);
for ($i = 0; $i < $len; $i++) {
if ($sum <= 0) {
$sum = $numbers[$i];
} else {
$sum += $numbers[$i];
}
if ($sum > $max) {
$max = $sum;
}
}
return $max;
}
echo getGreatestSumOfSubArray([1, -2, 3, 10, -4, 7, 2, -5]);
