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

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 2

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('');
}