Friday, April 4, 2014

Maximum segment sum in PHP

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
 */
    function maxsegsum (array $arr, $sz, &$beg, &$end)
    {  
       $maxe = $arr[0];          /* maximum ending here 
                              * cumulative sum */
       $maxs = $arr[0];          /* maximum so far */
       $beg_tmp = 0;
   
       for ($i = 1 ; $i < $sz ; $i++)
       {
          if ($maxe < 0)
          {
             $maxe = $arr[$i];   
             $beg_tmp = $i;
          }
          else
          {
             $maxe += $arr[$i];
          }
   
          if ($maxe >= $maxs)
          {
             $beg = $beg_tmp;
             $end = $i;
             $maxs = $maxe;   
          }
       }
       return $maxs;
    }

 $a = array(1, -2, 3, -2, 4);
 $beg = 0;
 $end = 0;
 $sum = maxsegsum ($a, 5, $beg, $end);
 
 print "Value of begin: $beg and value of end: $end <br>";
 print $sum;
?>

No comments:

Post a Comment