My intuition is that I should make the number of members in each partite set as close as possible, then remove all the edges within each partite set. So the answer I gave is:
If $n$ is even, max = $\binom n 2 - 2 \binom {\frac n 2} 2$.
If $n$ is odd, then max = $\binom n 2 - \binom {\frac {n-1} 2} 2 - \binom {\frac {n+1} 2} 2$.
Is this valid? If so, how do I justify it? If not, why?
EDIT: Just came up with something. In order to maximize the number of edges, the bipartite subgraph of $K_n$ should be a complete bipartite subgraph. The number of edges in a complete bipartite subgraph is $pq$, where $p$ and $q$ are the number of members in each partite set respectively. The goal is to maximize $pq$ subject to the constraint that $p + q = n$. Using the method of Lagrange multipliers, it can be deduced that $pq$ is maximized when $p = q = \frac n 2$. Would this be a valid argument?
Lagrange is not wellsuited for the discrete nature of the problem.
Any bipartite subgraph of $K_n$ with $p$ and $q$ vertices can be extended to $K_{p,q}$, having $pq$ edges. If $n$ is even then $$ pq=\frac14((p+q)^2-(p-q)^2)\le \frac14(n^2-0)$$ with equality if both $p+q=n$ and $p-q=0$, i.e., $p=q=\frac n2$.
If $n$ is odd, we cannot have $p+q=n$ and $p-q=0$ at the same time, so $$pq =\frac14((p+q)^2-(p-q)^2)\le\begin{cases}\frac14(n^2-1^2)&\text{if $p\ne q$}\\\frac14((n-1)^2-0^2)&\text{if $p+q\ne n$}\end{cases}$$ with equality in the first branch for $p=\lfloor \frac n2\rfloor$, $q=\lceil\frac n2\rceil$ or vice versa, and equality in the second branch for $p=q=\lfloor \frac n2\rfloor$. As the first is $\ge$ the second and the formula also holds for even $n$, we can summarize that the maximal number of edges is $$ \frac14\left\lfloor\frac n2\right\rfloor\left\lceil\frac n2\right\rceil. $$