TopCoder problem "MaxKTrace" used in TCO06 Qual 1/3/8 (Division I Level Three)

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

Returns: 15

There is only 1 possible 3 x 3 submatrix, so we simply return 1+5+9.

{
"12",
"93"
}

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

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9897&pm=6048

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Dynamic Programming