Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in $\mathcal{O}(k)$ time, evaluate $f$ and also get a list of which $k$:s are active (i.e. we can characterize the full subdifferential at any $x$ easily).
If all the breakpoints are known beforehand, I think we can solve this analytically in $\mathcal{O}(k^2)$ time. But what if they're not? Is a fast analytic solution still possible? Can we perhaps find the breakpoints easily? Especially interested in the case where each $f_k$ is a convex polynomial.