최대 부분 직사각형

면접 대비

시간 제한1초메모리 제한128 MB

요약

정수로 이루어진 N 곱하기 N 행렬에서 원소 합이 가장 큰 직사각형 부분 영역을 찾아 그 합을 출력한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 배열, 누적 합, 행렬
정답자: 아직 제출이 없습니다

문제

양수와 음수가 섞인 2차원 정수 배열이 주어진다. 부분 직사각형은 전체 배열 안에 놓인, 크기가 $1 \times 1$ 이상인 연속된 직사각형 영역을 말한다. 직사각형의 합은 그 직사각형에 포함된 모든 원소의 합이다. 이 문제에서 합이 가장 큰 부분 직사각형을 최대 부분 직사각형이라고 부른다.

예를 들어, 다음 배열에서

최대 부분 직사각형은 왼쪽 아래에 있는

 9 2
-4 1
-1 8

이며, 그 합은 15이다.

입력

입력은 $N \times N$ 크기의 정수 배열을 나타낸다. 첫 줄에는 정사각형 2차원 배열의 크기를 나타내는 양의 정수 $N$ 이 하나 주어진다. 이어서 배열을 이루는 $N^2$ 개의 정수가 공백(스페이스와 줄바꿈)으로 구분되어 주어진다. 이 정수들은 행 우선(row-major) 순서로, 즉 첫 번째 행의 값들을 왼쪽에서 오른쪽으로, 그다음 두 번째 행의 값들을 왼쪽에서 오른쪽으로 나열하는 식으로 주어진다. $N$ 은 최대 100까지 가능하다. 배열의 각 정수는 $[-127, 127]$ 범위에 있다.

출력

최대 부분 직사각형의 합을 출력한다.

예제2

예제 1

입력

4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1

8 0 -2

예상 출력

예제 2
입력
```
1
5
```
예상 출력
```
5
```