Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Problem 7. Sequence of Maximal Sum
- //Write a script that finds the sequence of maximal sum in given array.
- <!DOCTYPE html>
- <html>
- <head>
- <meta charset="UTF-8">
- <title></title>
- </head>
- <body>
- <form action="SequenceOfMaximalSum.php" method="post">
- <input type="text" name="text">
- <input type="submit" value="enter!">
- </form>
- </body>
- </html>
- <?php
- //$myString = $_POST['text'];
- $myArray=array(2, 3, -6, -1, 2, -1, 6, 4, -8, 8);//explode(" ", $myString);
- $max = $myArray[0];
- $maxEnd = $myArray[0];
- $longSequence = 1;
- $currentSequence = 1;
- $start = 0;
- $startTemp = 0;
- //Kadane's algorithm
- for ($i = 1; $i < count($myArray); ++$i)
- {
- if ($myArray[$i] + $maxEnd >$myArray[$i])
- {
- $maxEnd = $myArray[$i] + $maxEnd;
- $currentSequence++;
- }
- else
- {
- $maxEnd = $myArray[$i];
- $startTemp = $i;
- $currentSequence = 1;
- }
- if ($maxEnd > $max)
- {
- $max = $maxEnd;
- $longSequence = $currentSequence;
- $start = $startTemp;
- }
- }
- for ($i = $start; $i < $start + $longSequence; ++$i)
- {
- echo $myArray[$i].' ';
- }
- ?>
Advertisement
Add Comment
Please, Sign In to add comment