
ZOJ Problem Set  1449
Given a cube of positive and negative integers, find the subcube with the largest sum. The sum of a cube is the sum of all the elements in that cube. In this problem, the subcube with the largest sum is referred to as the maximal subcube. A subcube is any contiguous subarray of size 1x1x1 or greater located within the whole array. As an example, if a cube is formed by following 3x3x3 integers: 0 1 3 1 3 1 3 1 1 Then its maximal subcube which has sum 31 is as follows: 7 4 1 5 3 2
Each input set consists of two parts. The first line of the input set is a single positive integer N between 1 and 20, followed by NxNxN integers separated by whitespaces (newlines or spaces). These integers make up the array in a plane, rowmajor order (i.e., all numbers on the first plane, first row, lefttoright, then the first plane, second row, lefttoright, etc.). The numbers in the array will be in the range [127,127]. The input is terminated by a value 0 for N.
The output is the sum of the maximal subcube.
3
31 Source: Asia 1997, Shanghai (Mainland China) 