Strategy
The following linear-time algorithm adopts the strategy of hovering around $0$, by choosing either positive or negative numbers based on the sign of the partial sum. It preprocesses the list of numbers; it computes the permutation of the input on-the-fly, while performing the addition.
Algorithm
- Partition $a_1, \ldots, a_n$ into a two lists, the positive elements $P$ and the negative elements $M$. Zeros can be filtered out.
- Let $Sum=0$.
- While both lists are non-empty
- $~~~~~~$If $Sum>0$ { $Sum:=Sum+\text{head}(M)$; $M:=\text{tail}(M)$; }
- $~~~~~~$else { $Sum:=Sum+\text{head}(P)$; $P:=\text{tail}(P)$; }
- When one of the two lists becomes empty, add the rest of the remaining list to $S$.
Correctness
Correctness can be established using a straightforward inductive argument on the length of the list of numbers.
First, prove that if $a_1, \ldots, a_n$ are all positive (or all negative), and their sum does not cause overflow, then nor do the prefix sums. This is straightforward.
Second, prove that $Sum$ is within bounds is an invariant of the loop of the algorithm. Clearly, this is true upon entry into the loop, as $Sum=0$. Now, if $Sum>0$, adding a negative number that is within bounds to $Sum$ does not cause $Sum$ to go out of bounds. Similarly, when $Sum\le0$ adding a positive number that is within bounds to sum does not cause $Sum$ to go out of bounds. Thus upon exiting the loop, $Sum$ is within bounds.
Now, the first result can be applied, and together these are sufficient to prove that the sum never goes out of bounds.
-2^(n-1)
to2^(n-1)-1
. It of course requires two's complement and well defined overflow behavior, but in a language like C# it should work. $\endgroup$