之前遇到过这样一道题目:一个任意长度的整数数组{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);