You could do it via a set in a very similar way. The binary search approach works mostly in a redundancy-elimination fashion. You could store the set of "non-redundant" pairs (lastElement, Sum). A pair (x, y) is redundant if there is a pair (z, t) with z <= x and t > y (smaller last element, bigger sum). If you maintain the no-redundant pairs invariant, you'll have a list of pairs that, when sorted by first field, give increasing values in the other field. Once you've figured what pair needs to be inserted (if any at all) after having processed the current number, you also need to clean stuff up: that is, look for pairs that following the insertion of this new one have become redundant. This might appear as potentially linear per element, and it indeed may be, only that it amortizes overall: as you insert at most one pair at once, you can't, overall, delete more than N pairs. The main difference between this and the normal case is that here you can have further redundancies after inserting a pair (in the binary search case the one thing that you replace is precisely what would be redundant if looked upon as a set of pairs of lengths and values) and that neither of the dimensions allows for a nice indexing (as opposed to before when the length was bounded by N)