Find the maximum result after collapsing an array with subtractions

Question

Given an array of integers, I need to reduce it to a single number by repeatedly replacing any two numbers with their difference, to produce the maximum possible result.

Example1 - If I have array of [0,-1,-1,-1] then performing (0-(-1)) then (1-(-1)) and then (2-(-1)) will give 3 as maximum possible output

Example2- [3,2,1,1] we can get maximum output as 5 { first (1-1) then (0-2) then (3-(-2)}

Can someone tell me how to solve this question?

Answer 1

The goal is to find the maximum result after iteratively substracting two numbers in an array.

The problem is mainly at the algorithmic level.
It is clear that the final result is bounded by the sum of the absolute values:

Bound = sum_i abs(a[i])

According to the rule x - y, the signs may change frequently. The algorithm must focus on maximizing the sum of absolute remaining values.

The key point is to consider what happens when we decide to pair two numbers. If the signs of the numbers are different, the result will have a maximum absolute value, and we can decide the sign. For example, if the two values are (-5, 10), we will get 15 or -15. Associating numbers with a different sign, we just have to select the final sign in such a way that it is different from the sign of another number, for example the neighboor one.

The consequence is that if not all the signs are equal, we can manage that the result is equal to the bound. For example:

1 2 -3 4 5 -6 7 -> pair 2 and -3
1 -5 4 5 -6 7   -> pair 1 and -5
-6 4 5 -6 7
-10 5 -6 7
15 -6 7
-21 7
28 = Bound

If all the signs are equal, the bound cannot be attained. However, it is possible to minimize the loss by selecting as first number the one with the lowest absolute value. For example:

 3 4 1 2 2  -> pair 1 and 2
 3 4 -1 2   -> pair -1 and 2
 3 4 -3
 3 -7
 10 = Bound - 2*1

The same procedure can be used if all signs are negative. The point is that after this first "operation", we get a new bound, which can be attained thanks to the "sign rule".

In this situation (all signs equal), the result is equal to the bound minus twice the minimum absolute value.

Of course, one has to treat the n = 1 case separately : result = a[0];

From that, writing a programme is rather easy.

Answer 2

Consider an "anchor" an element we chose to string an arbitrary number of subtractions to.

Then clearly:

(Anchor1 - neg1 - neg2 - neg3...) - (Anchor2 - pos1 - pos2 - pos3...)

is optimal if

Anchor1 = max(array) and Anchor2 = min(array)

JavaScript code demonstrating the method by comparing it with brute force as well as Damien's great method (might not correctly handle arrays with all identical elements):

function bruteForce(A){
  if (A.length == 1)
    return A[0]
  let best = -Infinity
  for (let i=1; i<A.length; i++){
    for (let j=0; j<i; j++){
      let A1 = A.slice()
      let A2 = A.slice()
      A1[i] -= A1[j]
      A1.splice(j, 1)
      A2[j] -= A2[i]
      A2.splice(i, 1)
      best = Math.max(
        best, bruteForce(A1), bruteForce(A2))
    }
  }
  return best
}

function f(A){
  let max = [-Infinity, -1]
  let min = [Infinity, -1]
  
  A.map(function(x, i){
    if (x > max[0])
      max = [x, i]
    if (x < min[0])
      min = [x, i]
  })
  
  let restPos = 0
  let restNeg = 0
  
  A.map(function(x, i){
    if (i != max[1] && i != min[1]){
      if (x >= 0)
        restPos += x
      else
        restNeg += x
    }
  })
  
  return (max[0] - restNeg) - (min[0] - restPos)
}

function damien(A){
  let absSum = 0
  let minAbs = Infinity
  let allSignsEqual = true
  let firstSign = A[0] > 0
  
  A.map(function(x, i){
    absSum += Math.abs(x)
    minAbs = Math.min(minAbs, Math.abs(x))
    if ((x > 0) != firstSign)
      allSignsEqual = false
  })
  
  return allSignsEqual ? absSum - 2*minAbs : absSum
}

var n = 6
var m = 10

for (let i=0; i<100; i++){
  let A = []
  for (let j=0; j<n; j++)
    A.push(~~(Math.random()*m) * [1,1][~~(Math.random()*2)])
  let a = bruteForce(A)
  let b = f(A)
  let c = damien(A)
  if (a != b || a != c)
    console.log(`Mismatch! ${a}, ${b}, ${c} :: ${A}`)
}

console.log("Done")