《剑指Offer》-42.连续子数组的最大和

题干

输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个正数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为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]);