ThreeMines | Topcoder Archive

Problem Statement

A Company that Makes Everything (ACME) has entered the surface mining business. They bought a rectangular field which is split into cells, with each cell having a profit value. A mine is a non-empty rectangular region, and the profit of a mine is equal to the sum of the values of all its cells. ACME wants to extract ore from three different non-overlapping mines. You are to choose these mines to maximize the total profit.

You are given a String[] field where each character represents the profit value of a single cell. Characters 'a' to 'z' correspond to the numbers 0 through 25 and characters 'B' to 'Z' correspond to numbers -1 through -25. The jth char in the ith element of field is the profit value of the cell at row i, column j.

Definition

Class:: ThreeMines
Method:: maximumProfit
Parameters:: String[]
Returns:: int
Method signature:: int maximumProfit(String[] field)
(be sure your method is public)

Constraints

field will contain between 1 and 30 elements, inclusive.
Each element of field will contain between 1 and 30 characters, inclusive.
Each character of field will be from the set 'a'..'z' and 'B'..'Z'.
All elements of field will contain the same number of characters.
field must contain at least 3 cells.

Examples

```
{
"bbbb",
"bBBB",
"BBbb",
"BBBB"}
```
```
Returns: 7
```
One of the optimal solutions is the following: One mine contains all cells in the first row, the second mine contains the cell (1, 0), and the third mine contains the cells (2, 2) and (2, 3).
```
{"cfCBDCbcdZb"}
```
```
Returns: 14
```
A single row example.

{"d", "c", "B", "m", "Z", "h", "g", "B", "z", "G", "H", "b", "Y"}

Returns: 54

A single column example.

{
"hBhh", 
"BBBB",
"BBBB", 
"hBhh", 
"hBhh"}

Returns: 62

This test has only one solution.

```
{
"BB", 
"BB"}
```
```
Returns: -3
```
It is possible for the maximum possible profit to be negative.

{
"ZcabcaacacabcbbbcababacaccbZaa",
"acaaccccacbccbaaccabaccaacbZbc",
"bcbaacbcbbccbbcbabbbbaZcbcbccb",
"cccacbabccbZbcbabaacbbZcbacbab",
"cacbabbcabbabbcacbcbbcaacaabbc",
"bacZcacaaccbabbcccccabcaacbaca",
"cbcccacabcabacaccacaZbbcbcacbb",
"cZbbbcaacbaacaabZcaccbcZccbbab",
"Zcababaacbbbbccbcbbaccacacbbcc",
"cZcccaaabbcbcbccccbcbaabbbccbb",
"bbcaacacabccababacbccacccbbaba",
"cccbbcaZabccacabbccccabbabbbab",
"bbbacbccbbcaabaaabccbcaabcacaa",
"cbbababbccccbcccbaacacccaabaac",
"aaccaccaccbabbccaaaacbacccacca",
"bbbcabcabZZcabcabbaacZbaaabaZb",
"aaabbabcabaaacbcccccbbcabcccbc",
"bbbaccbacacaccbbaccabacbbbaaac",
"acaaacccbabbccbcbabbcbaaaccabb",
"bcaaaaabcbabaaabccacccbaacbbbc",
"bZcbcbcccaabccaabbccbababbbcca",
"cbbbbcccabcabcbacaaaaabbbbbcac",
"ccbbcbacacbbcacacbaabcbbacbaba",
"cbbbaabaabbbbaccabbcbcaccaaaac",
"abZcabaacbbcacbaaabccbabacacaa",
"aabccacbabaacaccccbbbbcccccaca",
"aabcbaaacbabcaccbaabbbabbabbca",
"ababcabaccaaaacccacbcbcabacbcb",
"bcaaaacabcabbbaccccccacabccacb",
"cbbabbbccaaaaacbccaabcbbccbacc"}

Returns: 671

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.