大小为n的数组中n-1个数的最大积

编程题

Posted by JAN on August 31, 2019

假设n个数的乘积为P,

  1. 如果P==0,计算除去0之后n-1个数的乘积设为Q,如果Q==0,说明数组中有2个0,那么n-1个数的积是0;如果Q<0,那么可以想到最大积是0;如果Q>0,那么Q是最大积;

  2. 如果P<0,除去最大的负数便能得到最大积;

  3. 如果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;
}