Максимальное произведение. В массиве, заполненном произвольными целыми числами, найдите два числа, произведение которых максимально. Вложенные циклы не используйте. Входные данные: На вход программе сначала подается значение n≤50000 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30000. Выходные данные: Выдайте два искомых числа в порядке неубывания.

Максимальное произведение двух чисел может получиться только в одном из двух случаев:

1. Произведение двух наибольших элементов массива.

2. Произведение двух наименьших элементов массива, если они отрицательные. Например, -30000 * -29999 даст большое положительное число.

Поэтому достаточно за один проход массива хранить:

• два максимальных числа;

• два минимальных числа.

Вложенные циклы не нужны. Сложность алгоритма — O(n), память — O(1).

#include 
#include 
#include 
using namespace std;
int main() {
    int n;
    cin >> n;
    int max1 = INT_MIN, max2 = INT_MIN;
    int min1 = INT_MAX, min2 = INT_MAX;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // Обновление двух наибольших чисел
        if (x > max1) {
            max2 = max1;
            max1 = x;
        } else if (x > max2) {
            max2 = x;
        }
        // Обновление двух наименьших чисел
        if (x < min1) {
            min2 = min1;
            min1 = x;
        } else if (x < min2) {
            min2 = x;
        }
    }
    long long productMax = 1LL * max1 * max2;
    long long productMin = 1LL * min1 * min2;
    int a, b;
    if (productMax >= productMin) {
        a = max2;
        b = max1;
    } else {
        a = min1;
        b = min2;
    }
    if (a > b) {
        swap(a, b);
    }
    cout << a << ' ' << b;
    return 0;
}

Например, для массива:

-10 -3 2 4 5

наибольшие числа — 5 и 4, их произведение равно 20.

Два наименьших числа — -10 и -3, их произведение равно 30.

Следовательно, ответ:

-10 -3