Задача g6_1042: Треугольник (VI международная олимпиада по информатике)

Дан треугольник, составленный из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке и заканчивающемся на основании треугольника.
Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
Число строк в треугольнике от 1 до 100.
Треугольник составлен из целых чисел от 0 до 99.

Входные данные:

Первым числом во входном файле с именем INPUT.TXT является количество строка в треугольнике. Пример файла исходных данных представлен ниже.

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Выходные данные:

В выходной файл с именем OUTPUT.TXT записывается только наибольшая сумма в виде целого числа. Ниже приведен OUTPUT.TXT для данных выше исходных данных.
30

Пример входных данных и правильной последовательности:

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

Решение g6_1042:
Эта задача предлагалась не только на международной олимпиаде, но и на областной в Самаре, несколько лет назад.
Первое решение, которое приходит в голову - рекурсия - неправильное. Здесь есть решение проще.
Для хранения треугольника заведем массив 100*100 (из элементов word, а почему не byte вы поймете позже), часть элементов которого останутся нулевыми. Начнем анализировать треугольник, двигаясь от предпоследней строки к первой (такой тип движения избавит нас от части частных случаев). Итак, смотрим на предпоследнюю строку. У нее по диагонали снизу есть два соседа (в треугольном массиве это число которое находится на 1 клетку ниже и число, на 1 клетку ниже и правее данного) - выберем из них наибольший и прибавим к значению элемента значение наибольшего из нижних соседей. Повторяя эту операцию для каждой строки до вершины и для самой вершины, в вершине (элемент (1;1)) получим искомую сумму. Если бы мы двигались сверху вниз, то возникал бы случай для крайних элементов, у которых всего один сосед.
Вот если бы нам надо было вывести маршрут, то было бы несколько сложнее, а так задача очень проста в реализации и несложна в понимании :)