Given a set $P$ of $n$ planar points, two axes and a real-valued score function $f()$ on subsets of $P$, the Optimal Planar Box Problem consists in finding a box (i.e. an axis-aligned rectangle) $H$ maximizing $f(H\cap P)$. We consider the case where $f()$ is monotone decomposable, i.e. there exists a composition function $g()$ monotone in its two arguments such that $f(A)=g(f(A_1),$ $f(A_2))$ for every subset $A\subseteq P$ and every partition $\{A_1,A_2\}$ of $A$. In this context we propose a solution for the Optimal Planar Box Problem which performs in the worst case $O(n^2\lg n)$ score compositions and coordinate comparisons, and much less on other classes of instances defined by various measures of difficulty. A side result of its own interest is a fully dynamic MCS Splay tree data structure supporting insertions and deletions with the dynamic finger property, improving upon previous results [Cort\'es et al., J.Alg. 2009].