Identifying the maximum predicate search pattern

The maximum predicate search algorithm is the counterpart to the minimum predicate search that is used to find the last (maximum) point in a sorted search space after which a monotonic boolean function (predicate) changes its value, assuming it changes only once. It is a very powerful technique that can solve many optimization and feasibility problems in logarithmic time.

These are generally easy or medium problems where we have a large sorted search space, and we need to define a predicate function that verifies if certain constraints are met. The goal is to find the last (maximum) value in the search space after which the result of the predicate function flips.

If the problem statement or its solution follows the generic template below, it can be solved using the maximum predicate search algorithm.