Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php
- /**
- * Using Kadane's algorithm
- * premshree, 07/17/10
- */
- function find_max_subarray($arr) {
- //start and end are the indices that we'll eventually return
- $start = 0;
- $end = 0;
- $sum = 0;
- // tstart and tend keep track of temp runs; tsum keeps track of
- // the sum of the temp run
- $tstart = 0;
- $tend = 0;
- $tsum = 0;
- $curr_pos = 0;
- foreach ($arr as $ele) {
- // temp run
- if ($tsum+$ele<=0) {
- $tsum = 0;
- $tstart = $curr_pos+1;
- } else {
- $tsum += $ele;
- $tend = $curr_pos;
- }
- // change indices based on temp run
- if ($tsum > $sum) {
- $sum = $tsum;
- $start = $tstart;
- $end = $tend;
- }
- $curr_pos++;
- }
- for ($i=$start; $i<=$end; $i++) {
- $ret[] = $arr[$i];
- }
- return $ret;
- }
- var_dump (
- find_max_subarray(
- array(0, 2, 4, -6, 6, 7, 9, -1, 1, -7)
- )
- );
- ?>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement