An Interesting Optimization Problem You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference between those integers; i.e., if the removed integers are $b$ and $c$, you put $|b - c|$ into the set again. You keep applying the operation until you are left with only a single number. So after $n - 1$ steps the game will terminate; you need to find out what is maximum value of the single number left in the end.
I am interested in seeing any polynomial time algorithm for the problem. Currently I don't have any idea about how to solve this problem in less than $\mathcal{O}(n !)$.
If you feel that there does not any polynomial time algorithm, could you please establish in which complexity class it lies? Is it NP complete?
Summarizing the main arguments: 


*

*You can never get more than maximum of $a_i$'s.    

*It seems like the number of different terminal values are at most $2^{n - 2}$.    

*Not every expression is valid. An expression corresponds to a combination of + and - signs assigned to integers in the array.   

*Keeping the difference $\geq$ 0 is the main source of difficulty.   

*If we assume that all the expressions are valid, then this problem can be converted to a NP complete problem: the SUBSET-SUM problem. But as not all the expressions are valid, this can give us better ideas/algorithms.

*Bill Bradley has proved the problem of finding the minimum is NP-hard and he has also shown the construction for point 2; the problem of finding the number of different terminal positions was raised by Johan Wästlund.

*Brendan McKay's comment extends the argument for finding the maximum is also NP hard. Hence currently we have managed to prove that the problem is NP hard. 

 A: [Edit: I had originally posted a proof that finding the minimum value was NP-hard; in the comments below, Brendan McKay pointed out how to convert that into a proof that finding the maximum value is NP-hard, which was the question asked by the original poster.  I have edited this to include a complete answer to the original question.]
Let's refer to the operation of replacing two values $b,c$ in a multiset by the single value $|b-c|$ as a "contraction"; the original poster asks if it is possible to find an ordering of repeated contractions that maximizes the final value.
In this post, we begin by asking if we can find the order with the minimum possible value.  Specifically, we try to determine whether the minimum value is zero or greater than zero.  We will show that deciding this question is NP-complete.  (We need to make it into a decision problem ("is it equal to zero?") rather than a minimization problem ("what's the smallest value?") to phrase it in terms of NP-completeness.)  We then show how to convert this result into a statement about the maximum rather than minimum value.
Also, to Johan Wastlund's comment above, a slight modification of the construction gives an $O(2^{n-2})$ lower on the maximum number of distinct values that can be produced (which I'll outline at the bottom).

Determining if the minimum value is zero is clearly in NP-- we can simply (non-deterministically) guess the correct pattern of steps to produce zero.  Showing that it is NP-complete takes a little more effort.  We will show this by a reduction from the partition problem.  
Take an instance of the partition problem with inputs $x_1,...,x_n$.  We are trying to find a subset $S\subseteq \{1,...,n\}$ such that $\sum_{i\in S}x_i=\sum_{i\not\in S}x_i$.
Set $M_1=M_2=2\sum_i x_i$.  Consider the multiset $\{M_1,M_2,x_1,...,x_n\}$.  Let $f(x,y)=|x-y|$.  Since we have taken $M_1$ to be so large, it follows that
$$f(\cdots(f(f(M_1,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_1-\sum_{j=1}^k x_{i_j}$$
and similarly for $M_2$.  
Claim: if there exists a subset $S$ that partitions the integers $x_1,...,x_n$, then the minimum value attained by repeated contractions is zero.
Proof: Assume that such an $S$ exists.  Then we can apply $f$ to $M_1$ and the elements of $S$ to get
$$M_1-\sum_{i\in S}x_i$$
and similarly with $M_2$ and the complement of $S$ to get
$$M_1-\sum_{i\not\in S}x_i$$
As our last step, we can subtract these and get zero.  Since the output value is non-negative, then the minimum value is zero.
Claim: if an ordering of repeated contractions produces a final value of zero, then we can produce a partition from this ordering in polynomial time.
Proof: The computation of the final value attained by the repeated contraction corresponds to the evaluation of $f$ on a binary tree with the leaf nodes labeled by $x_1,...,x_n$.  As pointed out in the comments above, we can "squash" this tree (in $O(n)$ time) and show that the output is equal to the sum $\sum_i \pm x_i$.  If we let $S$ correspond to the $x_i$ with a positive index, we have constructed the desired partition.

We have shown above that determining whether the smallest value is zero is NP-complete.  We now show that this implies the same complexity for the maximum.
Specifically, take $x_1,...,x_n$ and observe that the maximum possible value that can be achieved by repeated contraction is $\max_i x_i$.  We now ask the question: is the maximum final value achieved by repeated contraction equal to $\max_i x_i$, or is it strictly smaller?
We will show that deciding this question is NP-complete.  It is clearly in NP, since we can exhibit an ordering of contractions that achieves the maximum, if such an ordering exists.
To show that it is NP-complete, we will reduce from the problem of determining if there is an ordering of repeated contractions that equals zero.
Take the multiset $A=\{x_1,...,x_n\}$ and consider a new element $M=1+\sum_i x_i$. Let $B=A\cup \{M\}$.  Note that $M$ is the unique maximum over $B$.
We first show that if the maximum final value for the repeated contraction of $B$ is $M$, then the minimum repeated contraction of $A$ is 0.  If there exists a repeated contraction with final sum $M$, then any contraction that involves $M$ must be of the form $f(M,0)$ (otherwise the final sum would be strictly less than $M$) and vice versa.  Suppose that we replace $M$ by 0; the same pattern of contractions will now produce a final value of 0.  Therefore, we have produced a pattern of contractions on $A\cup \{0\}$ that gives a final value of zero.
In the other direction, we show that if the minimum final value for the repeated contraction of $A$ is 0, then the maximum value for $B$ is $M$.  Suppose that the minimum repeated contraction of $A$ is 0.  Then consider the identical pattern of contractions on $B$, which will leave us with $M$ and 0; the last contraction will produce $|M-0|=M$
Therefore, we can determine if the minimum final value of $A$ (which was arbitrary) is zero if an only if we can determine if the maximum final value of $B$ is $M$.
Therefore, the problem of determining if the maximum final value of a repeated contraction is equal to the maximum of the original set is NP-complete.

Johan Wastlund asked, as a function of $n$, what the maximum number of distinct values can be produced by applying $f$ in all possible combinations?  He suggested it might be $2^{n-2}$.  The construction above can be modified to show that there are at least this many possibilities.
Let $x_i=2^i$, for $i=1,...,n-2$.  Let $M_1=2^{n-1}$ and let $M_2=2^n$.  Since
$$M_z>\sum_{i=1}^{n-2}$$
(for $z=1,2$) then we still have
$$f(\cdots(f(f(M_z,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_z-\sum_{j=1}^k x_{i_j}$$
Let $S$ be the subset of indices subtracted from $M_1$.  Then we can construct the sum
$$f(M_1-\sum_{i\in S}^k x_{i},M_2-\sum_{i\not\in S}^k x_{i})= M_2-M_1+(\sum_{i\in S}^k x_{i})-(\sum_{i\not\in S}^k x_{i})$$
This sum assumes a distinct value for each subset $S$ of $\{1,...,n-2\}$, so there are at least $2^{n-2}$ distinct values.
A: This was meant to be a comment, but I don't have enough reputation to post one. Hopefully it might have something to do with an answer too (but I do not remember what polynomial time means). 
Assume for convenience $a_1 \leq a_2 \leq ... \leq a_{n-1} \leq a_n$. Let $m$ denote the max value of the number at the end of the game. Clearly $m$ is at most $a_n$. We could consider a dual problem: Save $a_n$ aside, and with the remaining numbers $a_1 \leq a_2 \leq ... \leq a_{n-1}$ play the same game, but this time trying to end up with the smallest possible number. Say that smallest number is $s$, so now we have $m = a_n - s$. An idea how to get $s$ would be as follows: It is of the form (abs value of) $a_{n-1}+e_{n-2}a_{n-2}+...+e_2 a_2 + e_1 a_1$ where $e_j=-1$ if the preceding partial sum is positive (so we aim to decrease it further), or $e_j=1$ if the preceding partial sum is negative (we aim to make it closer to $0$). Just an idea, I did not verify all details, meant a comment. 
Let me illustrate (since the meaning of preceding partial sum may not be clear). Say we start with $[2,7,17,19,35]$. Save $35$ aside and with the remaining numbers form $19-17-7+2$ (the $+2$ at the end because $19-17-7=-5<0$, and we want to make the $-5$ to move closer to $0$). Thus $19-17-7+2 = -3$, or (taking abs value) $s=3$. Finally $m=35-3=32$. If I follow the steps of the game instead, it would look like this: $[2,7,17,19,35]$, $[2,7,2,35]$, $[2,5,35]$, $[3,35]$, $[32]$. 
