2차원 최대구간합 문제

2차원 평면에서 최대구간합을 구하는 문제.

 

row, col = map(int, input().split())
s = []

for i in range(0, row):
    s.append(list(map(int, input().split())))

for i in range(row):
    current_sum = 0
    for j in range(1, col):
        s[i][j] = s[i][j] + s[i][j-1]

max_sum = float('-inf')
for left in range(0, col):
    for right in range(left, col):    
        current_sum  = 0
        for r in range(0, row):
            if left == 0:
                current_sum += s[r][right]
            else:
                current_sum += (s[r][right] - s[r][left-1])
            
            max_sum = max(max_sum, current_sum)
            current_sum = max(0, current_sum)
print(max_sum)

 

문제 해결 아이디어는

 

격자 평면에서 좌우 구간을 모든 경우의 수를 설정 후 그 구간의 세로줄로 카데인 알고리즘을 적용한다.

가로 세로 n 인 정사각형 평면일 시

좌우 평면을 잡는 것이 n*2, 그 구간에서 카데인 알고리즘을 적용하는 것이 n 이므로 시간 복잡도는 O(n*3) 이다.