EDIT: Added an answer meeting the unique-sum requirement.
Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique.
Proof. Here's the reduction. First we describe the reduction to the problem without the requirement that the maximum is unique.
Fix a 3-CNF-SAT instance $\phi$. Assume WLOG that $\phi$ has more ...