최대 부분행렬 합

면접 대비

시간 제한2초메모리 제한128 MB

요약
N x M 정수 행렬에서 연속된 행과 열로 이루어진 부분 행렬 중 합이 최대인 값을 구하는 문제입니다.
난이도

보통10점 중 6점

유형
동적 계획법, 행렬, 배열, 누적 합
정답자
아직 제출이 없습니다

문제

N x M 행렬의 각 칸에 정수 하나가 적혀 있다. 이 게임에서는 연속한 행과 연속한 열로 이루어진 비어 있지 않은 부분행렬을 하나 고르고, 그 안에 있는 모든 정수의 합을 점수로 삼는다.

가능한 모든 부분행렬 중 점수가 가장 큰 값을 구하라.

입력

첫째 줄에 N과 M이 주어진다 (1 < N < 200, 1 < M < 200). 다음 N개의 줄에는 각 줄마다 M개의 정수가 주어진다. 각 정수는 -10,000 이상 10,000 이하이다.

출력

첫째 줄에 부분행렬 원소 합의 최댓값을 출력한다.

예제1

  1. 예제 1

    입력
    3 5
2 3 -21 -22 -23
5 6 -22 -23 -25
-22 -23 4 10 2
    예상 출력
    16