[算法]求最大连续子数组和的PHP程序

之前遇到过这样一道题目:一个任意长度的整数数组{1,-3,4,5,6,7,-6,10,-15},求最大的连续子数组和。这里就是4,5,6,7,-6,10的和。这道题运用动态规划的思想,找以数组下标i位置的最大和Max[i]。
Max[i] = (Max[i-1] > 0) ? (Max[i-1] + Max[i] ) : Max[i];
之后在所有Max[i]中求一个最大值即可,时间复杂度为O(n),以下程序用php代码写出:

<?php  
function maxArr($arr) {  
  
    $max    = $arr[0]; //最大值  
    $endMax = $arr[0]; //以KEY结尾的最大值  
  
    foreach($arr as $key => $value) {  
        if($key == 0) {  
            //以0结尾作为开始,这里直接跳过  
            continue;  
        }  
  
        $endMax = ($endMax > 0) ?  ($endMax + $value) : $value;  //以$key结尾的数组最大值  
        $max    = ($endMax > $max) ? $endMax : $max;             //总的最大值  
    }  
    return $max;  
}  
//测试用例  
$test = array(-1,4,5,6,-10,12,-2,1);  
echo maxArr($test);  

发表评论

邮箱地址不会被公开。 必填项已用*标注


*