暴力求解最大子数组

function violentMax($array,$count,&$start,&$end) {
    $sum = 0;
    $max = 0;

    for($i=0; $i <= $count-1; $i++) {
        for ($j = $i; $j <= $count-1 ; $j++) { 
            $sum = 0;
            for($k = $i; $k <= $j; $k++) {
                $sum += $array[$k];
            }
            if ($sum > $max) {
                $start = $i;
                $end = $j;
                $max = $sum;
            }
        }
    }

    return $max;
}

$array = array(3,-1,2,5,-3,4,-6,-7,1,8,-3,5,9);
$count = count($array);
$start = 0;
$end = 0;
$max = violentMax($array,$count,$start,$end);
echo '<hr>';
echo $start;
echo '<hr>';
echo $end;
echo '<hr>';
echo $max;

上面方法的时间复杂度为O( n^2 );

分治策略实现最大子数组

<?php
class divideRule {
    public $left_pos;
    public $right_pos;
    public function divide($arr,$start,$end) {
        if ($start == $end) {
            return $arr[$start];
        } else {
            $mid = floor(($start+$end)/2);
            $left_max = $this->divide($arr,$start,$mid);
            $right_max = $this->divide($arr,$mid+1,$end);
            $middle_max = $this->middleMax($arr,$start,$mid,$end);
            if ($left_max >= $right_max && $left_max >= $middle_max) {
                return $left_max;
            } else if($right_max >= $left_max && $right_max >= $middle_max) {
                return $right_max;
            } else {
                return $middle_max;
            }

        }
    }
    public function middleMax($arr,$start,$mid,$end) {
        $left_sum = 0;
        $sum = 0;
        for($i = $mid; $i >= 0; $i--) {
            $sum = $sum + $arr[$i];
            if ($sum > $left_sum) {
                $left_sum = $sum;
                $this->left_pos = $i;
            }
        }
        $right_sum = 0;
        $sum = 0;
        for ($j = $mid+1; $j <= $end ; $j++) { 
            $sum = $sum + $arr[$j];
            if ($sum > $right_sum) {
                $right_sum = $sum;
                $this->right_pos = $j;
            }
        }
        $count_sum = $right_sum + $left_sum;
        return $count_sum;
    }
}


$array = array(3,-1,2,5,-3,4,-6,-7,1,8,-3,5,9);
$count = count($array)-1;
$rule_class = new divideRule();
$max = $rule_class->divide($array,0,$count);
echo $rule_class->left_pos;
echo $rule_class->right_pos;
var_dump($max);