学步园

给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合乘积中最大的一组，并写出算法的时间复杂度。

子数组最大乘积问题可以分为以下几种情况。  

1.数组中有多于一个零则最大乘积为0；
2.数组中只有一个零，而有奇数个负数，则最大乘积必定为0；
3.数组中只有一个零，而有偶数个负数，则最大乘积为除去0的元素的乘积；  
4.数组中没有零，而有奇数个负数，则最大乘积为除去绝对值最小的负数的乘积；  

5.数组中没有零，而有偶数个负数，则最大乘积为除去最小的正数的乘积。

只遍历一遍数组，因此时间复杂度为O(n)。

#include<iostream>
using namespace std;

int Max(int *d,int n)
{
	int n_zero=0;
	int n_neg=0;
	int maxneg=0;
	int minpos=0;
	int maxnegi=0;
	int minposi=0;
	int zeroi=0;
	int out;
	int max=1;
	
	for(int i=0;i<n;i++)
	{
		if(d[i]<0)
		{
			n_neg++;
			if(maxneg==0||maxneg<d[i])   //最大负数
			{
				maxneg=d[i];
				maxnegi=i;
			}
		}
		else if(d[i]==0)
		{
			zeroi=i;         
			n_zero++;
			if(n_zero>1)    //至少两个0
				return 0;
		}
		else
		{
			if(minpos==0||minpos>d[i])     //最小正数
			{
				minpos=d[i];
				minposi=i;
			}
		}
	}
		
	if(n_zero==1&&n_neg%2==1)
	{
		return 0;
	}
	else if(n_zero==1&&n_neg%2==0)
	{
		out=zeroi;
	}
	else if(n_zero==0&&n_neg%2==1)
	{
		out=maxnegi;
	}
	else if(n_zero==0&&n_neg%2==0)
	{
		out=minposi;
	}
	
	for(i=0;i<n;i++)
	{
		if(i!=out)
			max*=d[i];
	}
	return max;
}

int main()
{
    int a[10]={1,3,-2,4,6,3,-9,0,9,10};
	int max;
	max=Max(a,10);	
	cout<<"max: "<<max<<endl;	
	return 0;
}