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

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

75. Maximum Path Sum in a Diamond Grid

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:

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

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";


?>

Explanation:

Node Class Definition:

The Node class represents a node in a diamond-shaped structure.
Properties:

$left_part and $right_part store left and right child nodes.
$value stores the node’s value.
$largest caches the maximum sum of values in the subtree rooted at this node.

Constructor:

Initializes the node with a given value.

max_value() Method:

Returns the largest sum of values in the subtree.
Checks if $largest is cached; if so, it returns this value.
If it’s a leaf node, it returns the node’s value.
Recursively calculates maximum sums of the left and right subtrees.
Sets and returns $largest as the sum of $value and the greater of the left and right subtree sums.

Diamond Structure Initialization:

Initializes $diamond array, which stores the diamond’s structure.
Reads input lines, splits each line by commas, and populates $diamond.

Node Array Initialization:

Initializes a 2D array, $nodes, where each element is a Node object created from values in $diamond.

Connecting Nodes:

Connects nodes to form the diamond structure:

For nodes in the upper half of the diamond, sets left_part and right_part to the nodes below and to the right in the next row.
For nodes in the lower half, sets left_part and right_part to nodes directly below and to the left in the next row.

Maximum Sum Calculation:

Retrieves the top node of the diamond and displays the maximum sum of values within the diamond structure by calling max_value() on the top node.

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:

Flowchart:

For more Practice: Solve these Related Problems:

Write a PHP script to compute the maximum path sum in a diamond-shaped grid using dynamic programming.
Write a PHP script to traverse a pyramid-like array and determine the maximum sum path from the top to the base.
Write a PHP script to calculate the maximal sum path in a grid with variable row lengths using recursion.
Write a PHP script to analyze a diamond-shaped structure and output the maximum possible path sum by exploring all routes.

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.