使用排序方法求解 Maxium 成对积

Question

我试图通过首先对向量进行排序然后将向量的最后两个元素相乘来解决最大成对乘积问题。

它适用于较小的数字但不适用于 10^5 数字。

任何人都可以看看并提供帮助吗？

这是我的功能

long long MaxPairwiseProductFast(const vector<int> &number)
{
    long long result = 0;
    long n = number.size();
    result = number.at(n-1) * number.at(n-2);
    return result;
}

这是我的主要功能

int main()
{
    int n;
    cin>>n;
    vector<int>numbers(n);
    for(int i = 0; i <n; i++){
     cin>>numbers[i];
    }
   sort(numbers.begin(), numbers.end());

    long long result = MaxPairwiseProductFast(numbers);

    cout<<result<<"\n";

    return 0;
}

它适用于较小的范围，但即使在使用 long long 后也不适用于较大的范围

Answer 1

首先，您需要将向量的数据类型从 int 更改为 long long，在您将 vector<int>number 写入 vector<long long>number 的任何地方。

为了获得正确的输出，你需要做的另一个改变是，你必须考虑至少有两个更大的负数的情况。

例如：如果矢量包含：{-10, -5, -2, 0, 1, 2}。
您的程序将输出：1 * 2 = 2 作为答案。
但是，这种情况的答案将是：-10 * -5 = 50。

因此，更正后的计算方法为：

long long MaxPairwiseProductFast(const vector<long long> &number)
{
  long long result = 0;
  long n = number.size();
  if (n < 2) return 0;
  result = number.at(n-1) * number.at(n-2);
  result = max(result, number.at(0) * number.at(1));
  return result;
}

Answer 2

您不需要像其他答案所建议的那样更改所有数据类型。像这样修复你的乘法：

long long MaxPairwiseProductFast(const vector<int> &number)
{
    long long result = 0;
    long n = number.size();
    result = number.at(n-1) * (long long)number.at(n-2);
    return result;
}

问题是您将两个 int * int 相乘，生成 int，然后然后将其作为 long long 返回。您需要在 乘法之前投射其中之一，这样它将执行 long long 乘法并得到 long long 结果。

同时检查最小两个数字的乘积，正如 Bishal 所建议的那样，因为 -5 * -5 > 4 * 4

使用排序方法求解 Maxium 成对积

Solving Maxium Pairwise Product using Sort Method

c++

algorithm

vector

coursera-api