无序数组中，三个数的乘积最大

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)

输入,一个无序数组长度n,接着n个数

4
3 4 1 2

输出，最大的结果

24

---

ac1：(时间复杂度 O(nlogn) ,用到了排序，不符合O(n)的要求)

需要排序，然后根据数据内容计算最大乘积，
注意数据使用 long long , 而非int

#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <sstream>
#include <algorithm>

using namespace std;

const int INF = 0x7fffffff;

typedef long long int LL;

bool cmp(LL a, LL b)
{
return a > b;
}

int main()
{
    freopen("in.txt", "r", stdin);
vector<LL> v;

int  n;
scanf("%d", &n);

int zCnt = 0;
int pCnt = 0;
int nCnt = 0;
for (int i = 0; i < n;i++)
    {
        LL tmp;
scanf("%lld", &tmp);
if (tmp > 0){
            pCnt++;
        }
else if (tmp == 0){
            zCnt++;
        }
else{
            nCnt++;
        }
        v.push_back(tmp);
    }

//sort(v.begin(), v.begin() + 3, cmp);
    sort(v.begin(), v.end(), cmp);

    LL ans = 0;
if (nCnt == 0) // 正数和0
    {
        ans = v[0] * v[1] * v[2];
    }
else if (pCnt == 0)  // 负数和0
    {
        ans = v[0] * v[1] * v[2];
    }
else if (zCnt >= n -2){ // 一正一负，两个正，两个负， ...
        ans = v[0] * v[n - 2] * v[n - 1];
    }
else{
// 三个正， 一正两负
        LL val1 = v[0] * v[1] * v[2];
        LL val2 = v[0] * v[n - 2] * v[n - 1];
        ans = max(val1, val2);
    }
cout << ans << endl;
return 0;
}