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

Last update on April 19 2025 11:50:32 (UTC/GMT +8 hours)

57. Maximum Sum of Contiguous Subsequence

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.

Visual 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";
}
?>

Explanation:

• Input Loop:
• The code uses a while loop to read lines from standard input until a line containing '0' is encountered.
• Convert Input to Integer:
• Each line read is converted to an integer using intval(), and this integer is stored in variable $n.
• Check for Termination Condition:
• If the value of $n is 0, the loop breaks, terminating further input processing.
• Initialize Arrays:
• Two arrays, $arr and $max_val, are initialized to store cumulative sums and maximum values, respectively.
• Nested Loop for Input Values:
• A for loop iterates from 0 to n-1, reading n integers from standard input and processing them.
• Each integer read is stored in variable $x.
• Initialize Iteration Variables:
• For each iteration, the current index $i in both arrays is initialized:
• $arr[$i] is set to 0 for cumulative sums.
• $max_val[$i] is initialized to a very low value (-1000000) to find maximum values.
• Update Cumulative Sums and Maximum Values:
• A nested loop iterates from 0 to the current index $i.
• The cumulative sum at each index $j is updated by adding the current input value $x.
• If the updated cumulative sum at $j is greater than the current maximum value at that index, it updates the maximum value.
• Output Maximum Value:
• After processing all inputs for the current test case, the code uses max($max_val) to find the highest maximum value calculated and outputs it.

Sample Input:
6
-4
-2
5
3
8

Sample Output:

16

Flowchart:

For more Practice: Solve these Related Problems:

• Write a PHP script to implement Kadane’s algorithm to find the maximum sum of a contiguous subarray.
• Write a PHP function to process an array of integers and return the highest contiguous subsequence sum.
• Write a PHP script to calculate the maximum sum subarray using dynamic programming techniques.
• Write a PHP script to handle arrays with all-negative numbers and determine the maximum contiguous sum.

PHP Code Editor:

Click to Open 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.