c++ - 如何找到给定数组中数字之间的最大乘法(限制为 100000 个数字)

Question

我正在尝试学习编程，在我们学校，我们有由机器人自动检查的练习。时间限制为 1 秒，内存限制为 1024 mb。 我尝试按升序对数组进行排序，然后将两个最高的数字相乘，但这太慢了(我的排序算法可能很慢，所以如果可能的话建议使用排序算法。) 这是我能做到的最快的方法:

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
int Maksimumas(int n, int X[]);
ofstream fr("U1rez.txt");
ifstream fd("U1.txt");
int main()
{
    int n, A[100000], B[100000], maxi=0;
    fd >> n;
    for (int i = 0; i < n; i++) {
        fd >> A[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            B[j] = A[i] * A[j];
        }
        maxi = Maksimumas(n, B);
        A[i] = B[maxi];
    }
    maxi = Maksimumas(n, A);
    fr << A[maxi];
    fr.close();
    return 0;
}
int Maksimumas(int n, int X[])
{
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        if (X[maxi] < X[i]) {
            maxi = i;
        }
    }
    return maxi;
}

对于任何想知道的人来说，n 是数组的大小。

Answer 1

您不需要对整个数组进行排序 - 您只需要两个最大的正数和两个最小的负数。两者之间的一切都是无关紧要的。

相反，您可以检查所有输入并跟踪两个最大的正数和两个最小的负数。在迭代结束时，将每一对相乘(如果找到)，然后比较结果。

// fd is opened like the original question, n is the number of elements to read
// that part is omitted for brevity

int max = -1; 
int preMax = -1;
int min = 1;
int preMin = 1;

int temp;
for (int i = 0; i < n; i++) {
    fd >> temp;
    if (temp > preMax) {
        if (temp > max) {
            preMax = max;
            max = temp;
        } else {
            preMax = temp;
        }
    } else if (temp < preMin) {
        if (temp < min) {
            preMin = min;
            min = temp;
        } else {
            preMin = temp;
        }
    }
}

int result = -1;
if (preMax >= 0) {
    result = preMax * max;
}
if (preMin <= 0) {
    int tempResult = preMin * min;
    if (tempResult > result) {
        result = tempResult;
    }
}

return result;