Дано числовий трикутник з N рядків. Написати програму, яка обчислює максимальну суму чисел, розміщених на шляху, що розпочинається із верхнього числа й закінчується на будь-якому числі в основі трикутника (максимум суми серед усіх таких шляхів). На кожному кроці до сусіднього по діагоналі числа можна рухатись лише вліво-вниз або вправо-вниз.

Ідея розв’язання. Задача є класичною задачею динамічного програмування. Найбільш ефективним є використання двох одновимірних масивів, в одному з яких буде міститись поточний рядок «максимальної» суми, а в другому – значення попереднього рядка.

Малюнок, який ілюструє роботу програми для випадку n=5

input.txt

output.txt

trikut.pas