How do you solve the following recurrence?
$$T(n) = \max_{i=1}^{n-1} T(i) + T(n-i) + i (n-i)$$
My ideas
I understand that if $i$ is too small then I am able to make one of the subproblems large but at the same time making $i(n-i)$ large would get smaller repeating problems.
I suspect that $T(n) = \mathcal{O}(n^2)$
Furhermore, my suspicion is that the maximum value is achieved when $i = \frac{n}2$ but I am not sure how to work with a reccurence with the $\max$ in it. Do I proceed using induction? If so then I tried the following but I am not sure how formal this is
Let $T(i) \le \frac{1}{2}i^2, \ \ \forall \ i < n$. The base case for $n=1$ is trivially true.
$$\implies T(n) \le \max_{i=0}^{n} \frac{1}{2}i^2 + \frac{1}{2}(n-i)^2 + i (n-i) $$
Differentiaing RHS w.r.t $i$ to find the maxima, I get that the maximum is at $i = \frac{n}2$. Substituting this value of $i$, we get
$$\implies T(n) \le \frac{1}{2}n^2$$
Am I correct? Is it possible to get a close form formula for $T(n)$?
First I think that your formula is $T(n)=\max\{T(i)+T(n-i)+i(n-i, 1\leq i\leq n-1\}$ for $n\geq 2$. (otherwise, you are defining $T(n)$ in function of $T(n)$). If you put $S(n)=T(n)-\frac{n^2}{2}$, you get the formula $S(n)=\max\{S(i)+S(n-i), 1\leq i\leq n-1\}$. Now computing some values $S(2),..$, and proceeding by induction, you get $S(n)=S(1)n$ for all $n$, and it is easy to finish.