Упражнения по PHP: вычисление максимального значения суммы передаваемых целых чисел

PHP: упражнение 75 с решением

Расположите целые числа (от 0 до 99) как узкую вершину холма, как показано на рисунке 1. Чтение таких данных, представляющих огромные, начиная с вершины и продолжая согласно следующему правилу до низа. Напишите программу PHP, которая вычисляет максимальное значение суммы передаваемых целых чисел.

Иллюстрированная презентация:

Входные данные: серия целых чисел, разделенных запятыми, указана в ромбах. В каждой строке нет пробелов. Пример ввода соответствует рисунку 1. Количество строк данных составляет менее 100 строк.

Пример вывода:
Максимальное значение суммы целых чисел, проходящих по правилу на одной строке.

Пример решения: -

PHP-код:

<?php
class Node {
    public $left_part;
    public $right_part;
    public $value;
    public $largest;
 
    public function __construct($value) {
        $this->value = $value;
    }
 
    public function max_value() {
        if ($this->largest !== null) {
            return $this->largest;
        }
        if (is_null($this->left_part) && is_null($this->right_part)) {
            return $this->value;
        }
        $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();
 
        return $this->largest = $this->value + max($left_part, $right_part);
    }
}
 
$diamond = array();
 
while ($line = trim(fgets(STDIN))) {
    $diamond[] = explode(',', $line);
}
 
$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]);
    }
}
 
for ($i = 0; $i < count($nodes); $i++) {
    for ($j = 0; $j < count($nodes[$i]); $j++) {
        $n = $nodes[$i][$j];
        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;
        }
    }
}
 
$top = $nodes[0][0];
 
echo $top->max_value() . "\n";
?>

Пример ввода:
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

Пример вывода:

 64 

Блок - схема:

Блок - схема:

Редактор кода PHP:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Напишите программу PHP, чтобы вырезать слова длиной от 3 до 6 символов из данного предложения не более 1024 символов.
Далее: написать программу PHP для печати количества комбинаций.