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

给定一个无序数组，包含正数、负数和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);
    vectorLL 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;
}