Pages

Wednesday, June 20, 2012

Value of selection

There is a 2 dimensional matrix M ( mxn ) of non-negative integers. A "selection" is defined as set of elements, satisfying the following condition:
If m>n then there is exactly one element from each column. Else, there is exactly one element from each row.
And sum of all elements of a selection is called its "value".
Find the selection with maximum "value" in O(m*n).

No comments: