What if is not convex? The simple binary search doesn't work. Check convexity: if adding one element always has diminishing (or constant) returns, function is convex.
Non-convex: sometimes adding more elements can be 'cheaper per unit'. The marginal cost isn't monotonic. For non-convex, try: randomization, different DP formulation, or accept that Aliens doesn't apply. Test convexity by computing the optimal values for different . If the differences are non-increasing, it is convex.