нахождение стоимости максимального пути (язык С)

[maxim3535]

в файл вводится двумерный массив
(например такой
4 5 6 8
6 4 3 1
8 9 5 3
3 5 6 3 )
и его размерность.
программа должна вычислить стоимость максимального пути при движении из верхнего левого угла в нижний правый, двигаясь только вправо и вниз, и вывести результат в файл.

делал вот так

while ((r!=m)&&(k!=n)) //цикл с предусловием, определяющим точку остановки исполнителя
	{
		if (a[r][k+1]>a[r+1][k]) //условие, определяющее шаг исполнителя вправо на 1
		{	sum+=a[r][k+1]; //сумматор стоимости пути
			k+=1; //переход исполнителя в соседнюю справа клетку
		}
		else //условие, определяющее шаг исполнителя вниз на 1
		{
			sum+=a[r+1][k]; //сумматор стоимости пути
			r+=1; //переход исполнителя в соседнюю слева клетку
		}

сказали, что это неправильно, т. к.
при матрице

5 1 2 3
3 2 1 2
1 3 4 2
100 3 2 1

выдаст неверный результат

помогите пожалуйста составить верный код!
P.S. в коде должна использоваться функция(любая)

[Somebody]

maxSum[r][c] = a[r][c] + max(a[r - 1][c], a[r][c - 1])

[Serge_Bliznykov]

Somebody, расшифруйте, пожалуйста, ваш ответ для TC..
(я то понимаю, что Вы говорите о том, что нужно задать ещё одну матрицу, которую заполнить максимальными достижимыми суммами, причём заполнять нужно начиная от финальной точки и двигаясь по матрице к начальной точке)


Это типичная задача на динамическое программирование.
Воспользуйтесь поиском по форуму. Думаю, что Вы легко найдёте примеры решения и объяснение алгоритма.