題干

輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中的一個或連續(xù)多個正數(shù)組成一個子數(shù)組。求所有子數(shù)組的和的最大值。要求時間復(fù)雜度為O(n)。

解題思路

思路一

從頭到尾逐個累加數(shù)字，初始化和為0，當(dāng)和為負(fù)數(shù)時丟棄和，使用下一個數(shù)字賦值，和為正數(shù)時繼續(xù)累加，每次累加都與最大值進(jìn)行比較，如果大于最大值，則替換，直到遍歷完后，得到連續(xù)累加和的最大值。

思路二

使用動態(tài)規(guī)劃的思想進(jìn)行分析，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

代碼實現(xiàn)

思路一

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