How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?
On the one hand, we have
$$
\begin{align*}
T(n) &amp;\geq n^2 + nT(n-1) \\ &amp;\geq n^2 + n(n-1)^2 + n(n-1) T(n-2) \\ &amp;\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + n(n-1)(n-2)T(n-3)
\end{align*}
$$
and so on. Assuming, for simplicity, a base case of $T(0) = 0$, this gives
$$
\begin{align*}
T(n) &amp;\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n(n-1)\cdots (1)^2 \\ &amp;=
n! \left(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \cdots + \frac{1}{0!} \right) \\ &amp;=
n! \left(n + \frac{1}{(n-1)!} + \frac{1}{(n-2)!} + \cdots + \frac{1}{1!}\right) \\ &amp;=
n! \left(n + e - 1 \right) - O(1).
\end{align*}
$$
This should also work as an upper bound. To prove this rigorously, choose an upper bound $S(n)$ for which you can prove $S(n) \leq n^2 + n(S(n-1) + S(0))$ as well as that $S(n)$ is convex. Convexity will ensure that the values of $m$ maximizing the sum $S(n-m) + S(m-1)$ are $m=1$ and $m=n$.