Задачи
Треугольник
Треугольник
На рисунке изображен треугольник из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника.
- Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
- Число строк в треугольнике больше 1 и меньше или равно 100.
- Треугольник составлен из целых чисел от 0 до 99.
Входные данные
Первым числом является количество строк в треугольнике. Ниже по строкам представлен сам треугольник, числа в строке разделены пробелом.
Выходные данные
Вывести наибольшую сумму на пути от вершины до основания треугольника.
Входные данные #1
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Выходные данные #1
30