[Home|Training|Problems|Contests|C Language] | [Login|Register] |

Problems Status Rank |
Problem 1032
Maximum Sum
Time Limit: 1000ms
Memory Limit: 65536kb Description
Given a cube of positive and negative integers, find the sub-cube with the largest sum. The sum of a cube is the sum of all the elements in that cube. In this problem, the sub-cube with the largest sum is referred to as the maximal sub-cube. A sub-cube is any contiguous sub-array of size 1 x 1 x 1 or greater located within the whole array. As an example, if a cube is formed by following 3 x 3 x 3 integers:
Then its maximal sub-cube which has sum 31 is as follows:
Input
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 N x N x N integers separated by white-spaces (newlines or spaces). These integers make up the array in a plane, row-major order (i.e., all numbers on the first plane, first row, left-to-right, then the first plane, second row, left-to-right, etc.). The numbers in the array will be in the range [-127,127]. The input is terminated by a value 0 for N. Output
The output is the sum of
the maximal sub-cube.
Sample Input
3 0 -1 3 -5 7 4 -8 9 1 -1 -3 -1 2 -1 5 0 -1 3 3 1 -1 1 3 2 1 -2 1 0 Sample Output
31 |

University of Science and Technology of China

Online Judge for ACM/ICPC

Processed in 0.9ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 0.9ms with 1 query(s).