I frequently think of problems on my own, and try to solve them.
But this simple problem got me dazzled!
You have a set A, size N, Ai upto 109.
You play N - 1 steps on it.
Each step, pick any 2 elements x, y and remove both of them. Add back abs(x - y) to A.
Print the max value possible at end.
I was thinking that DP might solve this, but I was wrong about the approach that was coming to my mind.
The ans can't be greater than max element, say M.
So find out the minimum possible value that you can have from the remaining N - 1 elements.
A simple DP can be used for this, but this approach is wrong :)
Can anyone solve this?