rjangelov

ArraysInPHP - //Problem 7. Sequence of Maximal Sum

Jun 25th, 2014
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PHP 1.17 KB | None | 0 0
  1. //Problem 7.    Sequence of Maximal Sum
  2. //Write a script that finds the sequence of maximal sum in given array.
  3. <!DOCTYPE html>
  4. <html>
  5.     <head>
  6.         <meta charset="UTF-8">
  7.         <title></title>
  8.     </head>
  9.     <body>
  10.         <form action="SequenceOfMaximalSum.php" method="post">
  11.         <input type="text" name="text">
  12.         <input type="submit" value="enter!">
  13.         </form>
  14.     </body>
  15. </html>
  16. <?php
  17. //$myString = $_POST['text'];
  18. $myArray=array(2, 3, -6, -1, 2, -1, 6, 4, -8, 8);//explode(" ", $myString);
  19. $max = $myArray[0];
  20. $maxEnd = $myArray[0];
  21. $longSequence = 1;
  22. $currentSequence = 1;
  23. $start = 0;
  24. $startTemp = 0;
  25. //Kadane's algorithm
  26. for ($i = 1; $i < count($myArray); ++$i)
  27. {
  28.     if ($myArray[$i] + $maxEnd >$myArray[$i])
  29.     {
  30.         $maxEnd = $myArray[$i] + $maxEnd;
  31.         $currentSequence++;
  32.     }
  33.     else
  34.     {
  35.         $maxEnd = $myArray[$i];
  36.         $startTemp = $i;
  37.         $currentSequence = 1;
  38.     }
  39.     if ($maxEnd > $max)
  40.     {
  41.         $max = $maxEnd;
  42.         $longSequence = $currentSequence;
  43.         $start = $startTemp;
  44.     }
  45. }
  46. for ($i = $start; $i < $start + $longSequence; ++$i)
  47. {
  48.     echo $myArray[$i].'&nbsp';
  49. }
  50. ?>
Advertisement
Add Comment
Please, Sign In to add comment