The idea for choosing the coefficients $a_i$ may come for considering the cases $n=2$ and $n=3$. Clearly LHS must be non-negative, and also clearly not all $a_i$ may be $+1$, since then LHS < RHS. For $n=2$ we can only try $x^2 - y^2 \geq (x-y)^2$, for $x\geq y > 0$, which checks. For $n=3$, if we try $x^2 - y^2 - z^2 \geq (x-y-z)^2$, that will require $x^2 \geq y^2 + z^2$, and that may never be the case (for example when $x=y=z$). However, if we try $x^2 + y^2 - z^2 \geq (x+y-z)^2 = x^2+y^2+z^2 +2xy-2xz-2yz$, that will require $z^2 + xy \leq xz+yz$, or $(z-x)(z-y) \leq 0$, which holds if $\min(x,y)\leq z\leq \max(x,y)$.

Let $x_1\geq x_2 \cdots \geq x_n\geq 0$. If $n$ is odd, let $m=n$. If $n$ is even, let $m=n+1$ and $x_{m}=0$. So we have to prove that there are $a_i\in\{-1,1\}$, such that for $x_i\geq 0$. So $m$ is odd. \[\sum_{i=1}^m a_i x_i^2\geq \left(\sum_{i=1}^m a_ix_i\right)^2\] Let $A_i$ the square $[0,x_i]\times [0,x_i]$. Let $V_i=A_i-A_{i+1}\forall 1\leq i\leq m-1$ and $V_m=A_m$. So $|V_i|=x_i^2-x_{i+1}^2$. Let $X$ be the union of $V_1,V_3,\cdots, V_m$. Then $|X|=x_1^2-x_2^2+\cdots-x_{m-1}^2+x_m^2$. Let $T_i=[x_{i+1},x_i]$, so $|X_i|=x_i-x_{i+1}$. Let $U$ the union of $T_1,T_3,\cdots,T_m$. Let $Y=U\times U$. $|U|=x_1-x_2+\cdots-x_{m-1}+x_m$, so $|Y|=(x_1-x_2+\cdots-x_{m-1}+x_m)^2$ $Y=U\times U$, so $Y$ is the union of all $T_i\times T_j=S_{i,k}$ with $i,j$ odd, and $V_i$ is the union of $T_i\times [0,x_i]$ and $[0,x_i]\times T_i$. Suppose $S_{i,j}\subseteq Y$ with $i\geq j$. Then $T_j\subseteq [0,x_i]$, so $S_{i,j}\subseteq T_i\times[0,x_i]\subseteq V_i\subseteq X$. We have an analogous case with $i\leq j$. $\Rightarrow Y\subseteq X$, so $|X|\geq |Y|$, and this is the inequality with $a_i=(-1)^{i+1}$. \[x_1^2-x_2^2+\cdots-x_{m-1}^2+x_m^2=|X|\geq |Y|=(x_1-x_2+\cdots-x_{m-1}+x_m)^2\]

If $n=1$, it is clear that $$a_1\cdot x_1^2=(a_1\cdot x_1)^2$$if we take $a_1=1$. We can assume, WLOG, that $i>j \implies x_i\geq x_j$. Therefore, we claim that taking $a_{2i-1}=1$ and $a_{2i}=-1$ works, which we will prove by induction. Let $k\in \mathbb{Z}^{+}$. Suppose that the inequality holds for $n=2k-1$. Now, if $n=2k+1$, we have: \begin{align*} x_1^2-x_2^2+\dots-x_{2k-2}^2+x_{2k-1}^2 &\geq (x_1-x_2+\dots-x_{2k-2}+x_{2k-1})^2 & \text{(1)} \end{align*}\begin{align*} x_{2k}(x_1-x_2+\dots-x_{2k-2}+x_{2k-1}-x_{2k}) &\geq x_{2k+1}(x_1-x_2+\dots-x_{2k-2}+x_{2k-1}-x_{2k}) & \text{(2)} \end{align*} From (2), we get: $$x_{2k}x_{2k+1}+x_{2k}(x_1-x_2+\dots-x_{2k-2}+x_{2k-1})-x_{2k}^2 \geq x_{2k+1}(x_1-x_2+\dots-x_{2k-2}+x_{2k-1}) \implies$$\begin{align*} -x_{2k}^2+x_{2k+1}^2 &\geq 2(-x_{2k}+x_{2k+1})(x_1-x_2+\dots-x_{2k-2}+x_{2k-1})+x_{2k}^2+x_{2k+1}^2-2x_{2k}x_{2k+1} & \text{(3)} \end{align*}Finally, adding (1) and (3), we get: $$x_1^2-x_2^2+\dots-x_{2k}^2+x_{2k+1}^2\geq (x_1-x_2+\dots-x_{2k}+x_{2k+1})^2$$The case where $n$ is even can be obtained by taking $x_{2k+1}=0$