PHP Exercises: Compute the maximum value of the sum of the passing integers

PHP: Exercise-75 with Solution

Arrange integers (0 to 99) as narrow hilltop, as illustrated in Figure 1. Reading such data representing huge, when starting from the top and proceeding according to the next rule to the bottom. Write a PHP program that compute the maximum value of the sum of the passing integers.

Pictorial Presentation:

Input: A series of integers separated by commas are given in diamonds. No spaces are included in each line. The input example corresponds to Figure 1. The number of lines of data is less than 100 lines.

Sample Output:
The maximum value of the sum of integers passing according to the rule on one line.

Sample Solution:

PHP Code:

<?php
// Definition of the Node class with properties for left and right child nodes, node value, and a cache for the largest sum
class Node {
    public $left_part;
    public $right_part;
    public $value;
    public $largest;
    
    // Constructor to initialize the node with a given value
    public function __construct($value) {
        $this->value = $value;
    }
    
    // Method to calculate and return the maximum sum of values in the subtree rooted at this node
    public function max_value() {
        // If the largest sum is already calculated, return it
        if ($this->largest !== null) {
            return $this->largest;
        }
        
        // If the node is a leaf node, return its value
        if (is_null($this->left_part) && is_null($this->right_part)) {
            return $this->value;
        }
        
        // Recursively calculate the maximum sum for left and right subtrees
        $left_part  = is_null($this->left_part)  ? -1 : $this->left_part->max_value();
        $right_part = is_null($this->right_part) ? -1 : $this->right_part->max_value();
        
        // Calculate the largest sum including the current node's value
        return $this->largest = $this->value + max($left_part, $right_part);
    }
}

// Initialize an empty array to store the diamond structure
$diamond = array();

// Read input from standard input (stdin) and populate the diamond array
while ($line = trim(fgets(STDIN))) {
    $diamond[] = explode(',', $line);
}

// Initialize an array of Node objects based on the diamond structure
$nodes = array();
for ($i = 0; $i < count($diamond); $i++) {
    for ($j = 0; $j < count($diamond[$i]); $j++) {
        $nodes[$i][$j] = new Node($diamond[$i][$j]);
    }
}

// Connect the nodes to form a diamond-shaped structure
for ($i = 0; $i < count($nodes); $i++) {
    for ($j = 0; $j < count($nodes[$i]); $j++) {
        $n = $nodes[$i][$j];
        // Assign left and right child nodes based on diamond structure
        if ($i < count($diamond)/2 - 1) {
            $n->left_part  = isset($nodes[$i + 1][$j])     ? $nodes[$i + 1][$j]     : null;
            $n->right_part = isset($nodes[$i + 1][$j + 1]) ? $nodes[$i + 1][$j + 1] : null;
        } else {
            $n->left_part  = isset($nodes[$i + 1][$j - 1]) ? $nodes[$i + 1][$j - 1] : null;
            $n->right_part = isset($nodes[$i + 1][$j])     ? $nodes[$i + 1][$j]     : null;
        }
    }
}

// Get the top node of the diamond structure
$top = $nodes[0][0];

// Display the maximum sum of values in the diamond structure
echo $top->max_value() . "\n";


?>

Sample Input:
8
4, 9
9, 2, 1
3, 8, 5, 5
5, 6, 3, 7, 6
3, 8, 5, 5
9, 2, 1
4, 9
8

Sample Output:

64

Flowchart:

Flowchart:

PHP Code Editor:

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

Previous: Write a PHP program to cut out words of 3 to 6 characters length from a given sentence not more than 1024 characters.
Next: Write a PHP program to print the number of combinations.