Please prove or disprove that, for symmetric matrix $A=A^T$, we have

$$ \max_x x^T A x \geq Tr(A) $$ where $x = x_1, x_2, ..., x_n]^T \in \mathbb{R}^n$, $x_i \in \{+1, -1\}, i = 1, ..., n$.

Please prove or disprove that, for symmetric matrix $A=A^T$, we have

$$\max_{x \in \{\pm 1\}^n} x^T A x \geq \mbox{Tr}(A)$$