문제

동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점수 따먹기라는 게임인데 그다지 재밌어 보이지는 않는다.

동주가 개발한 게임은 이렇다. 일단 N*M 행렬을 그린 다음, 각 칸에 -10,000 이상 10,000 이하의 정수를 하나씩 쓴다. 그런 다음 그 행렬의 부분행렬을 그려 그 안에 적힌 정수의 합을 구하는 게임이다.

동주가 혼자 재밌게 놀던 중 지나가는 당신을 보고 당신을 붙잡고 게임을 하자고 한다. 귀찮은 당신은 정수의 합이 최대가 되는 부분행렬을 구하여 빨리 동주에게서 벗어나고 싶다.

# 1749
import sys
input = lambda: sys.stdin.readline().strip()

# 1. sum
# 2. 부분 행렬 -> 직사각형으로 생각

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

prefix = [[0] * (m+1) for _ in range(n+1)]
max_sum = -10000 * 200 * 200

for i in range(1, n+1):
    for j in range(1, m+1):
        prefix[i][j] = arr[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
        
        for y in range(i):
            for x in range(j):
                now_sum = prefix[i][j] - prefix[y][j] - prefix[i][x] + prefix[y][x]
                max_sum = max(max_sum, now_sum)
                
print(max_sum)

백준 1749 점수따먹기