MaxKTrace | Topcoder Archive

Problem Statement

The digit in element i character j of mat will correspond to the value in row i column j of an N x N matrix. Choosing k rows and k columns determines a k x k submatrix of mat. To compute the trace of such a submatrix S, first extract S from mat and reindex the rows and columns maintaining the original order. Add together all values along the main diagonal of the reindexed matrix (values with the same reindexed row and column). Return the largest trace considering all possible k x k submatrices.

Definition

Class:: MaxKTrace
Method:: getLargest
Parameters:: String[], int
Returns:: int
Method signature:: int getLargest(String[] mat, int k)
(be sure your method is public)

Constraints

mat will contain between 1 and 50 elements, inclusive.
Each element of mat will contain exactly N digits ('0'-'9'), where N is the number of elements in mat.
k will be between 1 and N, inclusive, where N is the number of elements in mat.

Examples

```
{
"123",
"456",
"789"
}
```
```
3
```
```
Returns: 15
```
There is only 1 possible 3 x 3 submatrix, so we simply return 1+5+9.
```
{
"12",
"93"
}
```
```
1
```
```
Returns: 9
```
Any entry can be used as the 1x1 submatrix, so we choose the 9.

{
"12689",
"55555",
"55555",
"55555",
"55555"
}

Returns: 16

The best we can do here is 6+5+5 = 16.

{
"494599520389852", 
"303896953907791", 
"287493604901139", 
"149554299340006", 
"893640109028429", 
"564962730433253", 
"075854577852319", 
"453201529585621", 
"950489162577436",
"630040569640126", 
"415141646262027", 
"837673828874883", 
"785041862021729", 
"850806584119109", 
"217671590991247"}

Returns: 45

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.