找出每个子数组中的任意一个元素可以形成的最大乘积

Question

我正在尝试用 JavaScript 编写一个有效的算法来解决这个任务。请参阅以下输入数据和正确结果的示例：

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

它可以是任意数量的子数组和每个子数组中任意数量的元素。我已经发现，我可能应该只在每个子数组中留下最小值和最大值，我.map(a => [Math.min(...a), Math.max(...a)])使用.sort((a, b) => a[0] - b[0]).

现在我被困住了。可能有一种方法可以计算所有可能的产品，但我确信这不是解决此任务的有效方法。

请帮忙！

Answer 1

您发布的问题可以通过简单的算法来解决。我们只需要在迭代每个子数组时持续跟踪最大值/最小值即可。我们可以通过将当前最大/最小值与每个子数组中的最大/最小值相乘来不断找到下一个最大/最小值。当迭代结束时我们选择最大值。它的时间复杂度是O(n)其中n是数组中元素的总数（即每个子数组中元素数的总和）。

这是完整的代码。find_maximum_product函数不断跟踪最小值/最大值并最终返回最大值，并且它还不断跟踪乘数并返回它：

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

更新

更简单的版本，仅获取最大值，而不获取乘数：

/**
 * 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];
}