Hi!

Задачку придумал для любителей сочинять алгоритмы. Что-то
все кому ни дам, никто работоспособного алгоритма не дает
(т.е. дают быстрые но ошибочные). Не пойму, она
действительно что ли сложная ?

Исходные данные: матрица NxN, содержит числа. Надо найти
прямоугольник внутри оной матрицы, сумма числел в котором
была бы максимальна (размеры прямоугольника неизвестны).
Параллельные алгоритмы неинтересны, они точно есть на гугле.

Очевидно, что решение не может быть быстрее N^2 (по числу
элементов). Требуется найти алгоритм сложности не
медленнее N^3 (мой) и узнать, возможны ли более быстрые.

Для нагула идей имеет смысл решить одномерный вариант
задачи, когда выбирается (непрерывный) подмассив
одномерного массива с максимальной суммой элементов
за линейное время (эту задачку можно найти на гугле).

Mikhail