Changing the signs of the coefficients of a polynomial to make all the roots real We are given a polynomial 
$$P_n(x):=a_nx^n + a_{n-1}x^{n-1}+\cdots+a_1x+a_0$$ 
with real coefficients.

Questions.
$\boldsymbol{(i)}$ How can we determine if there are $\epsilon_1,\ldots,\epsilon_n\in\{-1,+1\}$ such that 
  $$P_n(x;\pmb{\epsilon}):=\epsilon_n a_nx^n + \epsilon_{n-1} a_{n-1}x^{n-1}+\cdots+\epsilon_1 a_1x+a_0$$ 
  has only real roots? Here $\pmb{\epsilon}=(\epsilon_1,\dots,\epsilon_n)$.
$\boldsymbol{(ii)}$ If there is a solution, how can we find it?

Obviously an exhaustive search is hopelessly slow.  This question might just possibly (on a good day) be of relevance to a problem on graph polynomials.
 A: A small complement to Francesco's answer:
A thorough discussion of the $R$ polynomials (called subdiscriminants which are special cases of subresultants) is in Chapter 4 of the book "Algorithms in Real Algebraic Geometry" by Basu, Pollack and Coste-Roy. They can be used for instance to give a (very complicated) proof of the eigenvalues of a real symmetric being real (see this MO answer). 
A: At least in principle, a solution is provided  by the following result due to J. Sylvester:

Theorem (Sylvester). For each natural number $n \geq 2$ there exists a set of at most $n-1$ polynomials with integer coefficients $$R_{n, \, 1}(X_1, \ldots, X_n), \ldots, R_{n, \, k(n)}(X_1, \ldots, X_n)$$
  such that the monic real polynomials of degree $n$ $$P(x)=x^n+a_{1}x^{n-1}+ \cdots + a_n$$
  having only real roots are precisely those for which $$R_{n, \, 1}(a_1, \ldots, a_n) \geq 0, \ldots, R_{n, \, k(n)}(a_1, \ldots, a_n) \geq 0.$$

This can be seen as a generalization of the well-known fact that a real quadratic monic polynomial $x^2+a_1x+a_2$ has only real roots if and only if its discriminant $$D_2(1, \, a_1, \, a_2)=a_1^2-4 a_2$$
is non-negative. In fact, for all positive integers $n$ we have $$R_{n, \, 1}(a_1, \ldots, a_n) = D_n(1, \, a_1, \ldots, a_n),$$
where $D_n$ is the discriminant of $P(x)$, whereas the other polynomials $R_{n, \,i}$ can be explicitly computed in terms of determinants extracted from the Sylvester matrix of $P$ and $P'$.
So, in order to answer your question, one must check whether $$R_{n, \, 1}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0, \ldots, R_{n, \, k(n)}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0$$
for some choice of $\epsilon_1, \ldots, \epsilon_n \in \{-1, \, 1 \}.$ From the computational point of view, the problem is that the number of non-zero coefficients in our polynomials rapidly increases with the degree: for instance, $R_{9, \,1}=D_9$ has $26095$ terms.   
For further details, see 
C. Niculescu, L. E.Persson: Convex Functions and their Applications: A Contemporary Approach, Appendix B.
A: Perhaps it is useful to observe that if $P_n$ has only real roots,
the same is true for its derivative?
