Hello All! I have a given array of numbers and I have to change the sign of numbers to find out the minimum sum. The minimum sum will be 0 or greater than 0. Here is couple of test cases 1. [ 1 , 2 , 3 , 2 , 4 ]. Changing the sign [ -1 , -2 , -3 , 2 , 4 ] so minimum sum will be 0. 2. [ 3 , 5 , 7 , 11 , 13 ]. Changing the sign [ -3 , -5 , 7 , -11 , 13 ] so minimum sum is 1.
So technically this problem boils down to divide the set into two subset and find out the minimum difference. I though of DP but the number of element in array could 10^5 so could some one please tell me how to solve this problem ? I didn't assume that number will be positive because it was not given in the problem. Regards Mukesh Tiwari --