算法:求n个正负整数里面最大的连续和

* *************************************************
* Created on :2011-12-11 17:35:48
* Encoding   :UTF-8
* Description: 求最大子串和
* 求任意N个正负整数里面最大的连续和,要求复杂度为O(n)
* 认为当所有输入都为负数时,最大子串和为0
* 测试序列array(-2, 1, 3, 9, -4, 2, 3, 5, -3, -4, 1, 3);
* 输出结果19
* ************************************************
*/
function getMaxSequenceSum(array $sequence)
{
  $maxSoFar = 0;
  $maxEndingHere = 0;
for ( $i = 0; $i < count($sequence); $i++ )
{
  $maxEndingHere = $maxEndingHere + $sequence[$i];
if ( $maxEndingHere < 0 ) {
  $maxEndingHere = 0;
} else {
if ( $maxEndingHere > $maxSoFar ) $maxSoFar = $maxEndingHere;
}
}
  return $maxSoFar;
}
$sequence = array(-2, 1, 3, 9, -4, 2, 3, 5, -3, -4, 1, 3);
$max = getMaxSequenceSum($sequence);
var_dump($max);

该题目有4种解法,复杂度分别为O(n*n*n) O(n*n) O(nlogn) O(n)
分别对应三次变量,记住当前和的两次遍历,使用分治算法和一次遍历算法。