The pattern you mention of using a tuple of key-value pairs is not that bad and it even has a name. The Perl people call it the Swartzian transform.

An alternative if you don't like that would be having the maximum-finding function receive an additional comparator argument, similarly to qsort.