Hi
I frequently think of problems on my own, and try to solve them.
But this simple problem got me dazzled!
Problem Description:
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.
My Approach:
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?
Happy Coding!
