8075 : 최대 부분 직사각형 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 크기의 정수 격자가 주어집니다.
이 격자에서 합이 최대가 되는 부분 직사각형 영역의 합을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 200$
• $-100 \le A_{ij} \le 100$
이 격자에서 합이 최대가 되는 부분 직사각형 영역의 합을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 200$
• $-100 \le A_{ij} \le 100$
입력 설명
첫째 줄에 행의 수 $N$과 열의 수 $M$이 공백으로 구분되어 주어집니다. ($1 \le N, M \le 200$)
다음 $N$개의 줄에 걸쳐 격자의 각 행이 주어집니다. 각 행은 $M$개의 정수로 구성됩니다. ($-100 \le A_{ij} \le 100$)
다음 $N$개의 줄에 걸쳐 격자의 각 행이 주어집니다. 각 행은 $M$개의 정수로 구성됩니다. ($-100 \le A_{ij} \le 100$)
출력 설명
합이 최대인 부분 직사각형의 원소 합을 첫째 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5
1 -2 3 4 -1
-1 2 -1 2 -3
2 1 -3 1 2
-1 3 2 -2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
13도움
행의 시작 인덱스 $r_1$과 끝 인덱스 $r_2$를 고정하고, 각 열의 합을 압축한 1차원 배열에 카데인(Kadane's) 알고리즘을 적용하면 $O(N^2 \cdot M)$에 해결할 수 있습니다.