DividingRectangle | Topcoder Archive

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

```
{"11911103"}
```
```
Returns: 108
```
```
{"123","456","789"}
```
```
Returns: 3264
```
```
{"7","9","3"}
```
```
Returns: 189
```
There is only one way to divide the rectangle.

{"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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.