Максимальная сумма в двумерном списке
Подскажите алгоритм для решения задачи:
Есть двумерный список (таблица).
Нужно от левого верхнего угла добраться до правого нижнего и значения (через которые мы перемещаемся) нужно складывать.
Но задача в том, что нужно определить максимально возможное такое суммарное число.
Можно перемещаться либо вниз, либо направо (сколько угодно раз, лишь бы в итоге было максимальное суммарное число).
Например дана такая таблица:
listt = [[2, 7, 8, 0],
[2, 1, 1, 3],
[0, 3, 12, 2],
[2, 1, 5, 4]]
После обхода самая максимальная сумма равна 39 (т.е. 2, 7, 8, 1, 12, 5, 4)
Какой здесь алгоритм нахождения максимальной суммы?
Нужно каждый элемент сравнивать с предыдущими со всеми возможными?
А если массив будет намного больше, как тогда решать?
P.S. как это реализовать без использования методов, просто циклом и условным оператором?
Ответы (1 шт):
Алгоритм очень простой: в каждую ячейку (новой матрицы) записывать сумму числа в этой ячейки и максимального из двух чисел сверху и слева от неё.
Уточнение: не тех чисел, которые в матрице изначально, а постепенно, начиная с левого верхнего угла. Т.о. в каждой ячейке будет максимально возможная сумма.
Т. е. в результате вторая матрица получится такая:
listt = [[2, 9, 17, 17],
[4, 10, 18, 21],
[4, 13, 30, 32],
[6, 14, 35, 39]]
В итоге справа внизу получается необходимый результат.