最大子数组

暴力求解最大子数组

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
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 );

分治策略实现最大子数组

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);