문제
N x M 격자에 정수가 채워져 있을 때, 부분 직사각형의 합이 최대인 값을 구하라.
입력
첫째 줄에 N, M, 이후 N줄에 M개의 정수가 주어진다.
출력
최대 부분 직사각형 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 4 1 2 3 4 -1 0 5 -3 2 -4 2 1 | 15 |
풀이
2D 누적합을 구한 뒤, 열 범위를 고정하고 카다네 알고리즘(1D 최대 부분배열)을 적용한다.
- 2D 누적합 배열을 구축한다
- 열 쌍 (c1, c2)을 모두 고정한다
- 각 열 쌍에서 행별 구간 합을 O(1)에 구하고, 카다네 알고리즘으로 최대 연속 합을 구한다
- 모든 열 쌍 중 최대값을 출력한다
핵심 아이디어: 2D 최대 부분배열을 열 고정 + 1D 카다네로 분해하면 O(R * C²)에 해결된다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day748BOJ1749점수따먹기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int rows = Integer.parseInt(st.nextToken());
int cols = Integer.parseInt(st.nextToken());
long[][] m = new long[rows + 1][cols + 1];
for (int i = 1; i <= rows; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 1; j <= cols; j++) {
m[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
m[i][j] = m[i - 1][j] + m[i][j - 1] - m[i - 1][j - 1] + m[i][j];
}
}
long ans = Long.MIN_VALUE;
for (int c1 = 1; c1 <= cols; c1++) {
for (int c2 = c1; c2 <= cols; c2++) {
long last = 0;
for (int r = 1; r <= rows; r++) {
long sum = m[r][c2] - m[r][c1 - 1] - m[r - 1][c2] + m[r - 1][c1 - 1];
last = max(last + sum, sum);
ans = max(ans, last);
}
}
}
System.out.println(ans);
}
static long max(long a, long b) {
return a > b ? a : b;
}
}복잡도
- 시간: O(R * C²)
- 공간: O(R * C)