이차원 배열의 원소로 양/음의 정수값이 주어질 때 부 배열(1*1 이상)중 합이 가장 큰 값을 구하는 것이 문제이다. 부 배열이란 인접한 원소로 직사각형을 이루는 배열을 말하고 합이란 부행렬의 원소 모두를 더하는 것이다.
예를 들어 , 다음 배열의 최대 부 배열은
0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2왼쪽 아래에 있는 다음 배열이고
9 2 -4 1 -1 8합은 15 이다.
입력의 첫 줄에는 정수 N 이 주어진다. 다음 줄에는 N^2 개의 정수가 공백 혹은 줄바꿈을 사이에 두고 주어진다.
주어지는 정수는 행 우선(row major)으로 간주한다. 즉 행 부터 채워지고 다음 열로 넘어가서 다음 행이 채워진다. N 의 크기는 최대 100 이고 주어지는 원소의 크기는 -127 에서 127 사이 수이다.(-127,127 포함)
입력 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 출력 15
출처: Greater New York 2001