What is the maximum value of $x^TAx$ subject to $x\in\{\pm1\}^n$? Let $A \in \mathbb{R}^{n\times n}$ be symmetric and positive definite. What is the following maximum?
$$\max_{x\in\{\pm1\}^n}x^T A x$$

My attempt: 
if all $a_{ij}\geq 0$, then 
\begin{equation}
\max_{x\in\{\pm1\}^n}x^TAx=\sum a_{ij}
\end{equation}
and in this case $x=[1\quad 1\quad\cdots\quad 1]'$ or $x=[-1\quad -1\quad\cdots\quad -1]'$.
if some $a_{ij}<0$, then situation is not clear, but we know that $x^TAx\leq\sum{|a_{ij}|}$.
For example:
\begin{equation}
A=
\begin{bmatrix}
 2 & 3  &  1    \\
 3 & 10 &  -8  \\
 1 & -8  &  17
\end{bmatrix}.
\end{equation}
\begin{equation}
\max_{x\in\{\pm1\}^n}x^TAx=49<\sum |a_{ij}|=53
\end{equation}
and in this case $x=[1\quad1\quad-1]'$ or $x=[-1\quad-1\quad1]'$. So idea is to sacrifice $2a_{13}$ since it is smaller than $2a_{23}$ and $2a_{12}$.
Is there any systematic way to tell the maximum of $x^TAx$ for any $n$ if $A$ is given? and if yes how to find $x$ that will give the maximum? Any suggestions are welcome :)

I found an answer, maybe will be useful for someone.
For details go to this paper: http://users.isy.liu.se/en/rt/claal20/Publications/bipartite_consensus.pdf
Here $A$ represents an undirected graph. If $A$ is structurally balanced (condition of structurally balanced given in the paper), then $\max x^TAx = \sum |a_{ij}|$ and we can find at which corner objective function achieves maximum. However, if $A$ is not structurally balanced, $\sum |a_{ij}|$ can never be achieved. In this case, we have to go through all corners numerically to find the maximum. 
For example,  $\begin{equation}
A=
\begin{bmatrix}
 2 & 3  &  1    \\
 3 & 10 &  -8  \\
 1 & -8  &  17
\end{bmatrix}
\end{equation}$ is structurally unbalanced so we can never achieve 53. However, $\begin{equation}
A=
\begin{bmatrix}
 2 & 3  &  -1    \\
 3 & 10 &  -8  \\
 -1 & -8  &  17
\end{bmatrix}
\end{equation}$ is structurally balanced and for $x=[1\quad 1\quad -1]'$ or $x=[-1\quad -1\quad 1]'$ we can achieve 53.
