PHP Exercises: Find the maximum sum of a contiguous subsequence from a given sequence of numbers a1, a2, a3, ... an

PHP: Exercise-57 with Solution

Write a PHP program to find the maximum sum of a contiguous subsequence from a given sequence of numbers a1, a2, a3, ... an. A subsequence of one element is also a continuous subsequence.

Input:You can assume that 1 ≤ n ≤ 5000 and -100000 ≤ ai ≤ 100000.
Input numbers are separated by a space.
Input 0 to exit.

Pictorial Presentation:

Sample Solution:

PHP Code:

<?php
// Loop to read input until a line with '0' is encountered
while ($line = fgets(STDIN)) {
    // Convert the input to an integer
    $n = intval($line);

    // Check if the value of $n is 0, and break the loop if true
    if ($n == 0) {
        break;
    }

    // Initialize arrays to store cumulative sums and maximum values
    $arr = array();
    $max_val = array();

    // Loop through each input value
    for ($i = 0; $i < $n; $i++) {
        // Read the next integer from standard input
        $x = intval(fgets(STDIN));

        // Initialize values for the current iteration
        $arr[$i] = 0;
        $max_val[$i] = -1000000;

        // Loop through the array to update cumulative sums and find maximum values
        for ($j = 0; $j <= $i; $j++) {
            // Update cumulative sum
            $arr[$j] += $x;

            // Update maximum value if the current cumulative sum is greater
            if ($max_val[$j] < $arr[$j]) {
                $max_val[$j] = $arr[$j];
            }
        }
    }

    // Output the maximum value among the calculated maximum values
    echo max($max_val) . "\n";
}
?>

Sample Input:
6
-4
-2
5
3
8

Sample Output:

16

Flowchart:

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a PHP program to test whether two lines PQ and RS are parallel.
The four points are P(x1, y1), Q(x2, y2), R(x3, y3), S(x4, y4).
Next: Write a PHP program to test the specified Circumference of C1 and C2 intersect.