Здравствуйте, kittown, Вы писали:
K>Hi!
K>Задачку придумал для любителей сочинять алгоритмы. Что-то
K>все кому ни дам, никто работоспособного алгоритма не дает
K>(т.е. дают быстрые но ошибочные). Не пойму, она
K>действительно что ли сложная ?
K>Исходные данные: матрица NxN, содержит числа. Надо найти
K>прямоугольник внутри оной матрицы, сумма числел в котором
K>была бы максимальна (размеры прямоугольника неизвестны).
K>Параллельные алгоритмы неинтересны, они точно есть на гугле.
K>Очевидно, что решение не может быть быстрее N^2 (по числу
K>элементов). Требуется найти алгоритм сложности не
K>медленнее N^3 (мой) и узнать, возможны ли более быстрые.
K>Для нагула идей имеет смысл решить одномерный вариант
K>задачи, когда выбирается (непрерывный) подмассив
K>одномерного массива с максимальной суммой элементов
K>за линейное время (эту задачку можно найти на гугле).
K>Mikhail
решениеАвтор: Quintanar
Дата: 28.10.04
