Suppose we have 3d vectors $v_1, v_2, \dots, v_n$ where typically $n$ is large (100 or so). Then we want to find a sequence of $\pm$ such that $|\pm v_1 \pm v_2 \pm \dots \pm v_n|$ is maximal. Note that it suffices to maximize $|v_1 \pm \dots \pm v_n|$. Clearly, we can try all combinations of $\pm$ and pick the one that gives the largest resultant vector, but trying all combinations takes $2^{n-1}$ attempts.
I have thought about decomposing each vector with respect to a basis ($x,y,z$ directions, for instance) but this doesn't make it any easier. To see why, take any basis $A, B, C$, then let $v_i = a_iA+b_iB+c_iC$ and see we need to maximize $|a_1 \pm \dots \pm a_n| + |b_1 \pm \dots \pm b_n| + |c_1 \pm \dots \pm c_n|$. The problem is the $\pm$ are not really independent, for example if we pick $a_1 + a_2$ then we must also have $b_1 + b_2$ and $c_1 + c_2$.
Edit: deleted due to incorrectness
Given a $3 \times n$ matrix $\rm V$, we would like to find
$$\bar {\mathrm x} := \arg \max_{\mathrm x \in \{\pm 1\}^n} \| \mathrm V \mathrm x \|_2^2 = \arg \max_{\mathrm x \in \{\pm 1\}^n} \mathrm x^\top \mathrm V^\top \mathrm V \,\mathrm x = \arg \max_{\mathrm x \in \{\pm 1\}^n} \mbox{tr} \left( \mathrm V^\top \mathrm V \,\mathrm x \mathrm x^\top \right)$$
Note that rank-$1$ matrix $\mathrm x \mathrm x^\top$ is symmetric, positive semidefinite and has $1$'s on its main diagonal. Relaxing the rank-$1$-ness, we have the following semidefinite program (SDP) in matrix $\mathrm X \succeq \mathrm O_n$
$$\begin{array}{ll} \text{maximize} & \langle \mathrm V^\top \mathrm V , \mathrm X \rangle\\ \text{subject to} & x_{ii} = 1\qquad \forall i \in \{1,2,\dots,n\}\\ & \mathrm X \succeq \mathrm O_n\end{array}$$
If $\rm V$ is such that the solution of the SDP above is rank-$1$, then we have solved the original problem.