给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大 输入描述: 无序整数数组A[n] 输出描述:
满足条件的最大乘积
思路:
这个可以分类讨论下
(1)三个数都是正数，找最大的三个正数
(2)两个正数一个负数，最小的两个正数和最大的一个负数
(3)一个正数两个负数，最小的两个负数，和最大的一个正数
(4)三个都是负数，找最大的三个负数
(5)取到零，结果就是为零
代码:
#include <stdio.h> #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int ll; ll a[100010]; vector<ll> p; vector<ll> ne; vector<ll> zero; int cmp(ll a1, ll a2){ return a1>a2; } int main(){ int n; ll ans=-20000000000000000; scanf("%d", &n); for(int i=0; i<n; i++){ cin>>a[i]; } for(int i=0; i<n; i++){ if(a[i]>0){ p.push_back(a[i]); } else if(a[i]<0){ ne.push_back(a[i]); } else{ zero.push_back(a[i]); } } sort(p.begin(), p.end()); sort(ne.begin(), ne.end()); sort(zero.begin(), zero.end()); int ph=p.size(), neh=ne.size(), z=zero.size(); if(ph>=3){ ans=max(p[ph-1]*p[ph-2]*p[ph-3], ans); } if(ph>=2&&neh>=1){ ans=max(ans, p[0]*p[1]*ne[neh-1]); } if(z>0){ ans=max(ans, (ll)0); } if(ph>=1&&neh>=2){ ans=max(ans, p[ph-1]*ne[0]*ne[1]); } if(neh>=3){ ans=max(ans, ne[neh-1]*ne[neh-2]*ne[neh-3]); } //printf("%lld\n", ans); cout<<ans<<endl; return 0; }
