如何在最多100000个元素的数组中找出乘积最大的两数（满足1秒时间限制与1024MB内存限制）

看起来你在解决数组两数最大乘积的问题时遇到了性能瓶颈，咱们一步步来拆解问题并优化：

你的当前代码的核心问题 #

你的代码采用了两层循环计算所有两两元素的乘积，再逐个找最大值，时间复杂度是O(n²)。当n=100000时，这意味着要执行约5e9次运算（100000*99999/2），远远超出了1秒能处理的运算量（一般CPU每秒能处理~1e8次简单运算），这才是速度慢的根本原因，而不是排序算法的问题。

更高效的思路：无需排序，线性时间解决 #

其实找数组中两数乘积的最大值，根本不需要排序或者计算所有乘积。我们只需要关注两种情况：

• 数组中最大的两个正数相乘，得到最大正乘积；
• 数组中最小的两个负数相乘（因为负负得正），可能得到比正数乘积更大的值。

只需要遍历一次数组，记录这四个值（最大的两个数、最小的两个数），最后比较这两组乘积的最大值即可，时间复杂度是O(n)，对于1e5的数据来说完全是瞬间完成。

优化后的O(n)解法代码 #

#include <iostream>
#include <fstream>
#include <algorithm> // 用于max函数
using namespace std;

int main() {
    ifstream fd("U1.txt");
    ofstream fr("U1rez.txt");
    
    int n;
    fd >> n;
    
    long long max1 = -1e18, max2 = -1e18; // 最大的两个数，初始设极小值
    long long min1 = 1e18, min2 = 1e18;   // 最小的两个数，初始设极大值
    
    for (int i = 0; i < n; i++) {
        long long num;
        fd >> num;
        
        // 更新最大的两个数
        if (num > max1) {
            max2 = max1;
            max1 = num;
        } else if (num > max2) {
            max2 = num;
        }
        
        // 更新最小的两个数
        if (num < min1) {
            min2 = min1;
            min1 = num;
        } else if (num < min2) {
            min2 = num;
        }
    }
    
    // 计算两种情况的乘积，取最大值
    long long result = max(max1 * max2, min1 * min2);
    fr << result;
    
    fd.close();
    fr.close();
    return 0;
}

注意：这里用long long是为了避免整数溢出，因为两个1e5级别的数相乘会超过int的范围（int一般是32位，最大约2e9）。

如果一定要用排序法：选高效的排序算法 #

如果坚持用排序后取数的思路，一定要用时间复杂度**O(nlogn)**的排序算法，比如：

• C++标准库的std::sort()：底层是经过优化的快速排序+插入排序组合（introsort），效率非常高，是工业界的首选；
• 自己实现的话可以选快速排序、归并排序或者堆排序，这些算法的效率都远高于冒泡、插入排序这类O(n²)的算法。

基于sort的解法代码 #

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

int main() {
    ifstream fd("U1.txt");
    ofstream fr("U1rez.txt");
    
    int n;
    fd >> n;
    long long* arr = new long long[n]; // 用动态数组避免栈溢出（1e5个int在栈上可能超出栈空间）
    
    for (int i = 0; i < n; i++) {
        fd >> arr[i];
    }
    
    sort(arr, arr + n);
    
    // 比较最后两个数的乘积和前两个数的乘积
    long long result = max(arr[n-1] * arr[n-2], arr[0] * arr[1]);
    fr << result;
    
    delete[] arr;
    fd.close();
    fr.close();
    return 0;
}

这里用动态数组new long long[n]是因为栈的空间有限（一般几MB），直接声明long long arr[100000]可能会导致栈溢出，动态分配更安全。

总结 #

• 优先选择O(n)的线性解法，效率最高，完全满足时间限制；
• 如果用排序，一定要用O(nlogn)的高效算法，C++的sort()是最省心的选择；
• 避免O(n²)的算法，对于n=1e5来说完全不可行。

内容的提问来源于stack exchange，提问作者emirisu