TopCoder problem "DividingRectangle" used in TCHS07 Alpha 3 (Division I Level Two)



Problem Statement

    

You are given a rectangle containing a number in each cell. You must divide it into three smaller non-overlapping rectangles in such a way that each cell of the original rectangle belongs to exactly one of the smaller rectangles. Each of the smaller rectangles must contain at least one cell.

The sum of a rectangle is the sum of the numbers in all of its cells. Return the maximum possible product of the sums of the three smaller rectangles. The original rectangle is given in the String[] rectangle. The j-th character of the i-th element of rectangle is the number contained in the cell in the i-th row and j-th column.

 

Definition

    
Class:DividingRectangle
Method:maxProduct
Parameters:String[]
Returns:long
Method signature:long maxProduct(String[] rectangle)
(be sure your method is public)
    
 

Constraints

-rectangle will contain between 1 and 50 elements, inclusive.
-Each element of rectangle will contain between 1 and 50 characters, inclusive.
-All elements of rectangle will contain the same number of characters.
-rectangle will contain at least 3 characters.
-Each element of rectangle will contain only digits ('0'-'9').
 

Examples

0)
    
{"11911103"}
Returns: 108
1)
    
{"123","456","789"}
Returns: 3264
2)
    
{"7","9","3"}
Returns: 189
There is only one way to divide the rectangle.
3)
    
{"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999"}
Returns: 421749281250

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7609

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10729&pm=7609

Writer:

gevak

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force