Составить программу по алгоритму «Поиск оптимального пути в треугольнике (на максимум)». Вход: нагрузки на вершины графа; Выход: максимальное суммарное значение нагрузок и путь ( последовательность вершин для достижения оптимального значения).

Описание метода:

Идея состоит в том, чтобы найти наибольшую сумму, заканчивающуюся в каждой ячейке последней строки, и вернуть максимум этих сумм.

Описание данных:

N размер массива

treugolnik массив целых чисел размером N для хранения треугольника

matr массив целых чисел размером N для хранения максимальных сумм

i, j целые переменные используемые для счетчиков

find_max_sum функция поиска оптимального пути в треугольнике (на максимум), на вход подается массив треугольника treugolnik, возвращает целое число являющееся максимальным путем

Код программы

#include iostream

using namespace std;

#define N 4

/...