최대 부분 직사각형
골드 I의견: 0
\(N \times M\) 크기의 격자가 주어진다. 격자의 각 칸에는 정수가 하나씩 적혀 있으며, 음수일 수도 있다.
이 격자에서 부분 직사각형이란, 연속한 몇 개의 행과 연속한 몇 개의 열이 만나는 칸들의 모임을 말한다. 즉, 어떤 행 구간 \(r_1 \le i \le r_2\)와 열 구간 \(c_1 \le j \le c_2\)를 고르면, 그 안에 들어가는 모든 칸 \((i, j)\)들이 하나의 부분 직사각형을 이룬다.
가능한 모든 부분 직사각형 중에서, 그 안에 들어 있는 수들의 합이 최대가 되도록 하는 직사각형을 골랐을 때의 합을 구하는 프로그램을 작성하시오. 직사각형은 비어 있을 수 없으며, 적어도 한 칸(\(1 \times 1\))은 포함해야 한다.
모든 칸의 값이 음수일 수도 있으므로, 답이 음수가 될 수도 있음에 유의하라 (이 경우 답은 격자에서 가장 큰 한 칸의 값이 된다).
- \(1 \le N, M \le 1\,000\)
- 각 칸의 값 \(A_{i,j}\)는 \(-1\,000 \le A_{i,j} \le 1\,000\)인 정수이다.
첫째 줄에 격자의 행의 수 \(N\)과 열의 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에는 격자의 각 행이 주어진다. 각 줄에는 \(M\)개의 정수가 공백으로 구분되어 주어지며, 이는 해당 행의 칸에 적힌 값을 왼쪽부터 차례대로 나타낸다.
부분 직사각형 안의 수들의 합으로 가능한 최댓값을 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 20점 | \(1 \le N, M \le 50\) |
Subtask 2 | 30점 | \(1 \le N, M \le 300\) |
Subtask 3 | 50점 | 추가 제한이 없다. |
4 5
0 -2 -7 0 0
9 2 -6 2 0
-4 1 -4 1 0
-1 8 0 -2 015\(2\)행부터 \(4\)행, \(1\)열부터 \(2\)열까지로 이루어진 직사각형을 고르면 \(9 + 2 - 4 + 1 - 1 + 8 = 15\)로 합이 최대가 된다.
2 2
-1 -2
-3 -4-1모든 칸의 값이 음수이므로, 가장 큰 한 칸인 \(-1\)만을 고르는 것이 최선이다.
2 3
1 2 3
4 5 621모든 값이 양수이므로 격자 전체를 고르는 것이 최선이며, 그 합은 \(1 + 2 + 3 + 4 + 5 + 6 = 21\)이다.
rip 작성
출처 지정되지 않음
평가 및 의견
최대 부분 직사각형
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최대 부분 직사각형