1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| <?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);
|