假设n个数的乘积为P,
-
如果P==0,计算除去0之后n-1个数的乘积设为Q,如果Q==0,说明数组中有2个0,那么n-1个数的积是0;如果Q<0,那么可以想到最大积是0;如果Q>0,那么Q是最大积;
-
如果P<0,除去最大的负数便能得到最大积;
-
如果P>0,除去最小的正数便能得到最大积;
#define DOUBLE_EPS 1e-15
double maxProduct(vector<double> num, int n) {
if (n < 1) return 0;
double p_min = DOUBLE_MAX, n_max = DOUBLE_MIN;
int p_index = 0, n_index = 0, z_index = 0;
int p_count = 0, n_count = 0, z_count = 0;
int delete_index = 0;
for (int i = 0; i < n; ++i) {
if (fabs(num[i]) < DOUBLE_EPS) {
z_index = i;
++z_count;
}
else if (num[i] > 0) {
++p_count;
if (num[i] < p_min) {
p_min = num[i];
p_index = i;
}
}
else if (num[i] < 0) {
++n_count;
if (num[i] > n_max) {
n_max = num[i];
n_index = i;
}
}
}
if (z_count) {
if (z_count - 1) return 0;
if (n_count & 0x01 == 1) return 0;
else delete_index = z_index;
}
if (n_count & 0x01 == 1) delete_index = n_index;
else delete_index = p_index;
double max_product = 1.;
for (int i = 0; i < n; ++i) {
if (i != delete_index) {
max_product *= num[i];
}
}
return max_product;
}