I was wondering about a problem where:
You are given an array $A$ of size $N$ where each element $A_i$ is a natural number $<10^9$.
You play a game here which lasts for $N-1$ steps.
In each step, you remove any $2$ elements from the array, say $A_i$ and $A_j$, and insert back $|A_i-A_j|$.
At end, one element will remain in the array $A$, and you have to print the maximum possible value of that element.
My Approach:
Lets sort the array $A$.
Now let $f(i, 0)$ be the minimum score when this game is played on first $i$ nos only.
Similarly, let $f(i, 1)$ be the maximum score when this game is played on first $i$ nos only.
Clearly, $f(N,1)$ is out answer.
Now, let
$$X=|A_i-f(i-1,0)|$$
$$Y=|A_i-f(i-1,1)|$$
Then,
$$f(i,0)=min(X,Y)$$
$$f(i,1)=max(X,Y)$$
This is a 2D dynamic programming solution, and I think it will work.
Can you prove it right or disprove if its wrong?
Thanks in advance :)
EDIT:
I know this is wrong. Can someone please provide some algorithm for this?