PRODUCT (Omówienie)

Solution

General Idea: To find the maximum product of exactly three numbers in an array, consider that:

• The maximum product could come from the three largest numbers (all positive or the least negative if all are negative).

• Alternatively, if there are negative numbers, the product of the two smallest (most negative) numbers and the largest positive number could be larger.

Thus, sort the array and calculate:

where a[0],a[1] are the two smallest and a[n-1],a[n-2],a[n-3] are the three largest numbers.

Time complexity: \mathcal{O}(n \log n) due to sorting.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
#define all(x) x.begin(), x.end()
#define Moageza ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

void solve() {
    int n;
    cin >> n;
    vec<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(all(a));
    cout << max(a[n-1]*a[n-2]*a[n-3], a[0]*a[1]*a[n-1]) << "\n";
}

signed main() {
    Moageza
    int t = 1;
    while(t--) solve();
    return 0;
}