폴리매스

농사꾼 오일러는 농사를 지을 땅이 없다. 다행히 뒷산에 주인이 없는 넓은 땅이 있었다. 지금부터 오일러가 해야 하는 작업은 농사를 지을 직사각형 모양 땅을 선별하는 것이다. 여러분은 오일러를 도와 주어야 한다.

땅은 격자로 되어있다고 가정하자. 각 땅(격자)에는 점수가 매겨 져 있다. 점수가 0인 땅은 평범한 땅이고 점수가 +인 땅은 좋은 땅이다. 점수가 -인 땅에는 쓰레기가 많아 주변 농사를 망친다. 오일러는 땅의 점수의 총 합이 가장 큰 땅을 원한다. 땅이 6 * 3일때 오일러가 얻을 수 있는 가장 큰 땅의 점수의 합을 구하시요.

-1  4  7 -8  6 -2

 9 -1 -6  1  2 -4

 4  -1  2  3 -4  1