Python: вычислить максимальное значение суммы передаваемых целых чисел

Python Basic - 1: Упражнение 61 с решением

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

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

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

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

Код Python:

import sys
print("Input the numbers (ctrl+d to exit):")
x = [list(map(int, l.split(","))) for l in sys.stdin]
dp = x[0]
 
for i in range(1, (len(x)+1)//2):
    _dp = [0]*(i+1)
    for j in range(i):
        _dp[j] = max(_dp[j], dp[j]+x[i][j])
        _dp[j+1] = max(_dp[j+1], dp[j]+x[i][j+1])
    dp = _dp
 
for i in range((len(x)+1)//2, len(x)):
    _dp = [0]*(len(dp)-1)
    for j in range(len(_dp)):
        _dp[j] = max(dp[j], dp[j+1]) + x[i][j]
    dp = _dp
print("Maximum value of the sum of integers passing according to the rule on one line.") 
print(dp[0])

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

 Введите цифры (Ctrl + D для выхода):
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

Блок - схема:

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

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

Предыдущий: Напишите программу на Python, чтобы вырезать слова длиной от 3 до 6 символов из данного предложения не более 1024 символов.
Далее: Напишите программу на Python, чтобы найти число комбинаций, которые удовлетворяют p + q + r + s = n, где n - это заданное число <= 4000, а p, q, r, s в диапазоне от 0 до 1000.