ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1146. Maximum Sum

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array.
As an example, the maximal sub-rectangle of the array:
0 −2 −7 0
9 2 −6 2
−4 1 −4 1
−1 8 0 −2
is in the lower-left-hand corner and has the sum of 15.

Исходные данные

The input consists of an N × N array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by N 2 integers separated by white-space (newlines and spaces). These N 2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [−127, 127].

Результат

The output is the sum of the maximal sub-rectangle.

Пример

исходные данныерезультат
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
15