1차원에서 합이 최대인 구간을 찾았으니 2차원에서 합이 최대인 직사각형도 같은 식으로 될 줄 알았다. 안 됐다.
-5 7 1
-5 3 2
2 3 2
여섯 겹 반복
일단 다 더해봤다.
mx = float('-inf')
for i in range(n):
for j in range(n):
for ii in range(i, n):
for jj in range(j, n):
cur = 0
for k in range(i, ii+1):
cur += sum(arr[k][j:jj+1])
if cur > mx:
mx = cur
r = [i, j, ii, jj]
왼쪽 위 모서리 두 개, 오른쪽 아래 모서리 두 개로 네 겹이고, 안에서 행을 도는 게 한 겹, sum 이 한 겹이다. 위 예시의 답은 18이고 1행 2열부터 3행 3열까지다.
1차원 방식을 그대로 옮겨보기
1차원에서는 arr[i] = max(arr[i], arr[i] + arr[i-1]) 이었다. 2차원이니 위와 왼쪽에서 오는 걸 다 보면 되지 않을까 해서 이렇게 썼다.
if i > 0 and j > 0:
arr[i][j] = max(arr[i-1][j] + arr[i][j],
arr[i][j-1] + arr[i][j],
arr[i-1][j-1] + arr[i-1][j] + arr[i][j-1] + arr[i][j],
arr[i][j])
elif i > 0:
arr[i][j] = max(arr[i-1][j] + arr[i][j], arr[i][j])
elif j > 0:
arr[i][j] = max(arr[i][j-1] + arr[i][j], arr[i][j])
세 번째 후보에서 arr[i-1][j-1] 을 한 번 더하는데, 그 값은 arr[i-1][j] 안에도 arr[i][j-1] 안에도 이미 들어 있다. 같은 칸을 여러 번 세게 된다.
더 근본적인 문제는 이 점화식이 만드는 게 직사각형이 아니라는 것이다. 1차원의 "i 에서 끝나는 구간"에 해당하는 게 2차원에는 없다. (i, j) 를 오른쪽 아래 모서리로 하는 직사각형은 폭과 높이가 따로 정해지므로, 값 하나에 최선을 담아둘 수가 없다.
셀에 print(f'{i}, {j}: Both') 같은 걸 넣어가며 어디서 어긋나는지 보려 한 흔적이 남아 있다.
한 축을 눌러 1차원으로 만들기
방향을 바꿨다. 직사각형은 왼쪽 열과 오른쪽 열이 정해지면 나머지는 위아래를 어디서 자를지 문제다. 그건 1차원 문제다.
def kadane2d(matrix):
rows = len(matrix)
cols = len(matrix[0])
max_sum = float('-inf')
for left in range(cols):
sum_array = [0] * rows
for right in range(left, cols):
for i in range(rows):
sum_array[i] += matrix[i][right]
cur_max = sum_array[0]
for i in range(1, rows):
cur_max = max(sum_array[i], cur_max + sum_array[i])
max_sum = max(max_sum, cur_max)
return max_sum
left 를 고정하고 right 를 오른쪽으로 넓힌다. 각 행에서 left 부터 right 까지의 합을 sum_array 에 담으면, 원래 격자가 세로 한 줄로 눌린다. 거기에 1차원에서 쓰던 걸 그대로 돌린다.
right 를 한 칸 넓힐 때 sum_array 를 처음부터 다시 만들지 않고 그 열만 더한다. 여기가 이 방식의 요점이다.
열 쌍을 고르는 게 두 겹, 행을 훑는 게 한 겹이다. 여섯 겹이 세 겹이 됐다.
2차원 문제를 2차원 점화식으로 풀려고 하다가, 한 축을 없애서 이미 아는 1차원 문제로 만드는 쪽이 답이었다.