Максимальная сумма

Помогите решить, пожалуйста, чего-то совсем запуталась(

Сегодня на страницах газеты «Математический досуг» была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

Напишите программу, которая по заданной таблице найдет искомый прямоугольник.

Формат ввода
В первой строке вводятся два целых числа m и n ( 2 <= m, n <= 300). Далее следует описание таблицы – m строк, каждая из которых содержит по n целых чисел a_i,j ( -10⁴ < a_i,j < 10⁴).

Формат вывода
В первой строке выведите целое число s – максимальную сумму чисел на границе искомого прямоугольника. Во второй строке выведите четыре натуральных числа: x1, y1, x2, y2 – координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь x – номер строки, а y – номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

0

Если "тупо в лоб", то O(n⁴)

0

Сообщение от Catstail Если "тупо в лоб", то O(n4)

Если тупо в лоб, то O(n^5), O(n^4) - с использованием префиксных сумм. Теоретически можно до O(n^3) уменьшить, что для питона все равно тяжеловато будет

0

Red white socks, хм... откуда пятая степень? Две координаты - левый верхний угол; еще две - длина и ширина.

0

Это вот эта же задача, только с минимальной суммой?

Прямоугольник и массив

1

Alexarh, ну почти та же. Вместо суммы элементов сумма только по границе

Добавлено через 2 минуты
Catstail, сумму тоже посчитать надо

Добавлено через 1 минуту
С префиксными суммами она считается за О(1), а в лоб О(n)

2

Red white socks, эх!... Но тогда - даже не пятая, а шестая. Ведь сумма - это O(n²) А, невнимательно читал. Там сумма полосы, а не прямоугольника. Тогда ОК

1

Сообщение от Red white socks Теоретически можно до O(n^3) уменьшить

там видимо еще нужно на что-то с логарифмом умножить.

Добавлено через 5 минут
а нет, в принципе если взять алгоритм Кадане, будет O(n^3).

1

eaa, вроде чистый эн-куб, но возможно вы и правы, в детали смогу вникнуть только вечером.

0