Advertisement
Guest User

Max subarray using Kadane's algorithm

a guest
Jul 17th, 2010
409
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PHP 0.94 KB | None | 0 0
  1.  
  2. <?php
  3. /**
  4.  * Using Kadane's algorithm
  5.  * premshree, 07/17/10
  6.  */
  7. function find_max_subarray($arr) {
  8.    //start and end are the indices that we'll eventually return
  9.    $start = 0;
  10.    $end = 0;
  11.    $sum = 0;
  12.  
  13.    // tstart and tend keep track of temp runs; tsum keeps track of
  14.    //  the sum of the temp run
  15.    $tstart = 0;
  16.    $tend = 0;
  17.    $tsum = 0;
  18.    $curr_pos = 0;
  19.  
  20.    foreach ($arr as $ele) {
  21.       // temp run
  22.       if ($tsum+$ele<=0) {
  23.          $tsum = 0;
  24.          $tstart = $curr_pos+1;
  25.       } else {
  26.          $tsum += $ele;
  27.          $tend = $curr_pos;
  28.       }
  29.  
  30.       // change indices based on temp run
  31.       if ($tsum > $sum) {
  32.          $sum = $tsum;
  33.          $start = $tstart;
  34.          $end = $tend;
  35.       }
  36.       $curr_pos++;
  37.    }
  38.  
  39.    for ($i=$start; $i<=$end; $i++) {
  40.       $ret[] = $arr[$i];
  41.    }
  42.    return $ret;
  43. }
  44.  
  45. var_dump (
  46.    find_max_subarray(
  47.       array(0, 2, 4, -6, 6, 7, 9, -1, 1, -7)
  48.    )
  49. );
  50. ?>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement