javascript - 您可以从 k 个整数中获得的最高乘积

Question

我正在解决以下问题:

Given an arrayOfInts, find the highestProduct you can get from k of the integers.

这是我迄今为止基于从 3 个整数中获取 highestProduct 的概括提出的解决方案。

var getHighestProductOfk = function (arrayOfInts, k) {
  if (arrayOfInts.length < k) {
    throw Error('Array should be higher than k');
  }

  highestProductArray = [arrayOfInts[0]];
  lowestProductArray = [arrayOfInts[0]];

  for (let i=1; i<k; i++) {
    highestProductArray[i] = highestProductArray[i-1]*arrayOfInts[i];
    lowestProductArray[i] = lowestProductArray[i-1]*arrayOfInts[i];
  }

  for(let i=1; i<arrayOfInts; i++) {
    let currentInt = arrayOfInts[i];

    for(let j=k-1; j>=0; j--) {
      highestProductArray[j] = Math.max(
        highestProductArray[j],
        highestProductArray[j-1]*currentInt,
        lowestProductArray[j-1]*currentInt
      );

      lowestProductArray[j] = Math.min(
        lowestProductArray[j],
        lowestProductArray[j-1]*currentInt,
        highestProductArray[j-1]*currentInt
      );
    }

    // highest number
    highestProductArray[0] = Math.max(highestProductArray[0], currentInt)

    // lowest number
    lowestProductArray[0] = Math.max(lowestProductArray[0], currentInt)
  }

  return highestProductArray[k-1];
}

知道我做错了什么吗？对于以下示例 [1, 10, -5, 1, -100]，结果是 -50 而不是 5000。最低的数字是 1，最高的是 1 而不是 -100 和 10

三个整数的最高乘积的解:

var getHighestProductOfThree = function (arrayOfInts) {
  if (arrayOfInts.length < 3) {
    throw Error('Array should be higher than 3');
  }

  let highestProductOfThree = arrayOfInts[0]*arrayOfInts[1]*arrayOfInts[2];

  let highestProductOfTwo = arrayOfInts[0]*arrayOfInts[1];
  let lowestProductOfTwo = arrayOfInts[0]*arrayOfInts[1];

  let highest = arrayOfInts[0];
  let lowest = arrayOfInts[0];

  for (let i=1; i<arrayOfInts.length; i++) {
    let currentInt = arrayOfInts[i];

    highestProductOfThree = Math.max(
      highestProductOfThree,
      highestProductOfTwo*currentInt,
      lowestProductOfTwo*currentInt
    );

    highestProductOfTwo = Math.max(
      highestProductOfTwo,
      currentInt*highest,
      currentInt*lowest
    );

    lowestProductOfTwo = Math.min(
      lowestProductOfTwo,
      currentInt*lowest,
      currentInt*highest
    );

    highest = Math.max(
      highest,
      currentInt
    );

    lowest = Math.min(
      lowest,
      currentInt
    );

  }

  return highestProductOfThree;
}

Answer 1

这是一个想法。对数字进行排序。接下来，从最大的正数中尽可能多地选择，最多 k 个。现在从形成比最小正数更大乘积的最小负数中选择最大的偶数组，我们将用它们替换它们。 (有一些边缘情况，例如只有一个负数和 k - 1 个正数)。

Pick 3 from [1, 10, -5, 1, -100]

Sort => [-100,-5,1,1,10]

Pick largest positives => 10 * 1 * 1

Pick largest even number of smallest negatives we can,
whose product is greater than the one replaced

  => (-100) * (-5) > 1 * 1

Answer => 10 * (-100) * (-5)