Find the maximum product that can be formed by taking any one element from each sub-array

Question

I am trying to write an efficient algorithm in JavaScript to solve this task. Please see the next examples of input data and correct results:

Array: [ [-3,-4], [1,2,-3] ] Result: (-4)*(-3) = 12
Array: [ [1,-1], [2,3], [10,-100,20] ] Result: (-1)*3*(-100) = 300
Array: [ [-3,-15], [-3,-7], [-5,1,-2,-7] ] Result: (-15)*(-7)*1 = 105

It can be any number of sub-arrays and any number of elements in each sub-array. What I already found is that I probably should leave only min and max values in the each sub-array, I did it using .map(a => [Math.min(...a), Math.max(...a)]) and sort them using .sort((a, b) => a[0] - b[0]).

And now I am stuck. Probably there is a way to calculate all possible products but I am sure that it's not an effective way to solve this task.

Please help!

Answer 1

Here is a top-down recurrence that could be adapted to bottom-up (a loop) and utilises O(n) search space.

Until I can complete it, the reader is encouraged to add a third return value in the tuple, largest_non_positive for that special case.

// Returns [highest positive, lowest negative]
// Does not address highest non-positive
function f(A, i){
  const high = Math.max(...A[i]);
  const low = Math.min(...A[i]);

  if (i == 0){
    if (low < 0 && high >= 0)
      return [high, low];
    if (low <= 0 && high <= 0)
      return [-Infinity, low];
    if (low >= 0 && high >= 0)
      return [high, Infinity];
  }

  const [pos, neg] = f(A, i - 1);
  
  function maybeZero(prod){
    return isNaN(prod) ? 0 : prod;
  }

  let hp = maybeZero(high * pos);
  let hn = maybeZero(high * neg);
  let ln = maybeZero(low * neg);
  let lp = maybeZero(low * pos);

  if (low < 0 && high >= 0)
    return [Math.max(hp, ln), Math.min(hn, lp)];

  if (low <= 0 && high <= 0)
    return [ln, lp];

  if (low >= 0 && high >= 0)
    return [hp, hn];
}

var As = [
  [[-3,-4], [1,2,-3]],
  [[1,-1], [2,3], [10,-100,20]],
  [[-3,-15], [-3,-7], [-5,1,-2,-7]],
  [[-11,-6], [-20,-20], [18,-4], [-20,1]],
  [[-1000,1], [-1,1], [-1,1], [-1,1]],
  [[14,2], [0,-16], [-12,-16]],
  [[-20, -4, -19, -18], [0, -15, -10],[-13, 4]]
];

for (let A of As){
  console.log(JSON.stringify(A));
  console.log(f(A, A.length - 1)[0]);
  console.log('');
}

Answer 2

The problem you post can be solved with a simple algorithm. We just need to keep tracking the maximum/minimum when iterating over each sub-array. We can keep finding the next maximum/minimum by multiplying the current maximum/minimum with the max/min value in each sub-array. We pick the maximum when the iterating is over. Its time complexity is O(n) where n is total number of elements in an array (i.e. sum of number of elements in each sub-array).

Here's the complete code. find_maximum_product function keeps tracking the minimum/maximum and returns the maximum eventually, and it also keeps tracking the multipliers and return it:

/**
 * arr: array of any number of sub-arrays and
 *      any number of elements in each sub-array.
 *      e.g. [[1, -1], [2, 3], [10, -100, 20]]
 */
function find_maximum_product(arr) {
  let max = 1;
  let min = 1;
  let max_multipliers = [];
  let min_multipliers = [];

  for (let i = 0; i < arr.length; i++) {
    const a = Math.max(...arr[i]);
    const b = Math.min(...arr[i]);

    const candidates = [max * a, max * b, min * a, min * b];
    max = Math.max(...candidates);
    min = Math.min(...candidates);

    let new_max_multipliers;
    let new_min_multipliers;

    switch (max) {
      case candidates[0]:
        new_max_multipliers = max_multipliers.concat(a);
        break;
      case candidates[1]:
        new_max_multipliers = max_multipliers.concat(b);
        break;
      case candidates[2]:
        new_max_multipliers = min_multipliers.concat(a);
        break;
      case candidates[3]:
        new_max_multipliers = min_multipliers.concat(b);
        break;
    }

    switch (min) {
      case candidates[0]:
        new_min_multipliers = max_multipliers.concat(a);
        break;
      case candidates[1]:
        new_min_multipliers = max_multipliers.concat(b);
        break;
      case candidates[2]:
        new_min_multipliers = min_multipliers.concat(a);
        break;
      case candidates[3]:
        new_min_multipliers = min_multipliers.concat(b);
        break;
    }

    max_multipliers = new_max_multipliers;
    min_multipliers = new_min_multipliers;
  }

  if (max >= min) {
    return [max, max_multipliers];
  }
  return [min, min_multipliers];
}

const arrays = [
  [
    [-3, -4],
    [1, 2, -3],
  ],
  [
    [1, -1],
    [2, 3],
    [10, -100, 20],
  ],
  [
    [-3, -15],
    [-3, -7],
    [-5, 1, -2, -7],
  ],
  [
    [14, 2],
    [0, -16],
    [-12, -16],
  ],
  [
    [-20, -4, -19, -18],
    [0, -15, -10],
    [-13, 4],
  ],
  [
    [-2, -15, -12, -8, -16],
    [-4, -15, -7],
    [-10, -5],
  ],
];

for (let i = 0; i < arrays.length; i++) {
  const [max, max_multipliers] = find_maximum_product(arrays[i]);
  console.log('Array:', JSON.stringify(arrays[i]));
  console.log('Result:', `${max_multipliers.join(' * ')} = ${max}`);
  console.log('');
}

---

UPDATE

Simpler version for just getting the maximum, not getting the multipliers:

/**
 * arr: array of any number of sub-arrays and
 *      any number of elements in each sub-array.
 *      e.g. [[1, -1], [2, 3], [10, -100, 20]]
 */
function get_maximum_product(arr) {
  return arr
    .map((a) => [Math.min(...a), Math.max(...a)])
    .reduce(
      (acc, current) => {
        const candidates = [
          acc[0] * current[0],
          acc[0] * current[1],
          acc[1] * current[0],
          acc[1] * current[1],
        ];
        return [Math.min(...candidates), Math.max(...candidates)];
      },
      [1, 1]
    )[1];
}

Answer 3

1. Sort values in arrays by their absolute value in descending order
2. Check the product of first array elements if its positive its the answer
3. Otherwise lets call product p and we know p < 0, so if we change some positive element to some negative element or vice verse we will improve answer
4. we can simply check all possible elements to change, for each array a element x we can check if p / a[0] * x is better than current result if it is we update our answer
5. *Special case: all elements in arrays are negative and we have odd number of arrays, then we simply sort in increasing order

Complexity: O(n log n) where n is total amount of elements across all arrays

Answer 4

The first thing to notice is that there are only two specific cases where it's not possible to get a positive product. So I think an algorithm should first check if those specific cases are happening, then call a different subalgorithm for each of the three possible situations:

1. it is possible to get a positive product, so we want to find the highest positive product;
2. one of the arrays is full of zeroes, so all products are zero;
3. it is impossible to get a positive product, because no array has both positive and negative numbers, and there is an odd number of arrays with only negative numbers, so we want to find the closest to zero negative product.

The second and third cases lead to trivial algorithms.

Let's consider the first case.

For every array, the only numbers that can be useful in the highest product are the highest positive number, and the lowest negative number. If an array only has positive numbers or only has negative numbers, then there is only one useful number in that array, which can be chosen immediately.

For all the remaining arrays, you have to choose whether to use the positive or the negative number. Ideally, you want to use the one with the highest absolute value; but if you do that for every array, then the result might be negative.

This leads to a linear algorithm:

1. For all of the remaining arrays, initially select the number with the highest absolute value
2. If the resulting product is positive, you're done.
3. If the resulting product is negative, then a compromise has to be done in one of the arrays. For every array, compute the "cost" of this compromise (equal to the difference between the absolute values of the two interesting numbers in that array, multiplied by the product of all the other selected numbers).
4. Finally, choose the array whose cost is the lowest, and change the chosen number in that array.

Here is an example execution of the algorithm on the list of arrays [[18,19,20,-23], [12,-10,9,8],[-10,-3],[5,3],[-10,-5]].

Here we notice that it is possible to find a positive solution, because at least one of the arrays contains both negative and positive numbers.

For the last three arrays we have no choice between positive and negative: so we can already choose -10, 5 and -10 as the three numbers for these three arrays. For the first array, we'll have to choose between 20 and -23; and for the second array we'll have to choose between 12 and -10.

So the final product will be: (20 or -23) * (12 and -10) * (-10) * 5 * (-10).

Ideally, we would prefer 23 to 20, and 12 to 10. That would result in: (-23) * 12 * (-10) * 5 * (-10)

Unfortunately, this is negative. So the question is: do we replace -23 with 20, or 12 with -10?

The cost of replacing -23 with 20 would be (23-20) * 11 * (10*5*10) = 33 * (10*5*10).

The cost of replacing 12 with -10 would be (12-10) * 21 * (10*5*10) = 42 * (10*5*10).

Finally, we choose to replace -23 with 20, because that is the less costly compromise.

The final product is 20 * 12 * (-10) * 5 * (-10).

Answer 5

1. Take the product of the highest number of all the arrays that have at least one positive number.

2. If there's an odd number of remaining arrays (with only negatives), find the one with the highest (closest to zero) negative number, and set its absolute aside.

3. Take the arrays that remain after step 2, take the product of their lowest number (furthest from zero), and multiply it by the products from step 1 and (if any) step 2.

(also, avoid 0 if it would be the chosen number)