题解 | #最大乘积# 数学

既然题目分别要求了O(n)和O(1)的时空复杂度，那么就简单扫一遍数组就好。

根据提议，要找到最大乘积，要么是三个最大的正数相乘，要么是两个最小的负数及一个最大的正数相乘。

遍历数组，及时更新几个变量即可，注意不能用int，会溢出。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int num;
        vector<int> nums;
        for (int i = 0; i < n; i++) {
            cin >> num;
            nums.push_back(num);
        }
	    // 分别保存三个最大的正数，两个最小的负数
        long long pNum1 = 0, pNum2 = 0, pNum3 = 0, nNum1 = 0, nNum2 = 0;
        for (const auto& x : nums) {
            if (x > 0 && x > pNum1) {
                pNum3 = pNum2;
                pNum2 = pNum1;
                pNum1 = x;
            } else if (x > 0 && x > pNum2) {
                pNum3 = pNum2;
                pNum2 = x;
            } else if (x > 0 && x > pNum3) {
                pNum3 = x;
            } else if (x < 0 && x < nNum1) {
                nNum2 = nNum1;
                nNum1 = x;
            } else if (x < 0 && x < nNum2) {
                nNum2 = x;
            }
        }
        cout << max(pNum1 * pNum2 * pNum3, pNum1 * nNum1 * nNum2) << endl;
    }
    return 0;
}