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.

Example

Let's consider the following problem as an example to better understand how to identify and solve a problem using the maximum predicate search algorithm.

Problem statement: You are given an array `ribbons`, where `ribbons[i]` denotes the length of the `ith` ribbon and a non-negative integer `k`. You can cut any of the ribbons in any number of segments of positive size or not cut them at all. Write a function to find and return the maximum length of ribbons so that you have `k` ribbons of that length. You can ignore any excess ribbons. Return `0` if you cannot obtain `k` ribbons of the same length.