Leetcode—Maximum Product Subarray

Leetcode—Maximum Product Subarray

這道花了本人近8個小時，昨晚3個小時，今天下午5個小時。終於修正了所有的BUG，而且達到了時間復雜度O(n)，這道題在Leetcode上通過率為16.3%，難度上屬於中等偏上。但網上貌似有的大神寫的代碼只用了不到100行就實現了，我也是看過別人寫的才有了自己的思路。接下來要好好整理，看懂大神的代碼，fighting！！！

廢話不多說，附上代碼，代碼風格非常丑陋。

int maxProduct(int A[], int n)
{
	int max;
	int temp;
	int i , j, k;
	int total = 1;
	vector p;							        //用‘0’為分界將A[]切割成若干段，將每個段內的最大值存入p中
	vector q;								//用q存取‘0’在A[]中的下標
	if (n == 1)
		return A[0];
	else if (n <= 0)
		return 0;

	for (i = 0; i < n; i++)
	{
		total *= A[i];
		if (A[i] == 0)
			q.push_back(i);
	}

	if (total>0)								//total > 0 肯定為最大的子串product
		return total;

	else if (total == 0)
	{

		if (q[0] != 0)							//!!!!!開頭不是一串0，0，0...
		{
			total = 1;
			for (j = 0; j < q[0]; j++)					//0～q[0]-1之間的最大值取出並存入p中
				total *= A[j];
			if (total>0)
			{
				p.push_back(total);
				total = 1;
			}
			else
			{
				max = total;
				temp = total;
				for (k = 0; k < q[0] - 1; k++)
				{
					total = total / A[k];
					if (total>max)
						max = total;
				}
				total = temp;
				for (k = q[0] - 1; k > 0; k--)
				{
					total = total / A[k];
					if (total > max)
						max = total;
				}
				p.push_back(max);
				total = 1;
			}
		}

		for (i = 1; i < q.size(); i++)				//q[0]～q[1];q[1]～q[2]....q[q.size-2]～q[q.size-1]
		{
			total = 1;
			for (j = q[i - 1] + 1; j < q[i]; j++)
				total *= A[j];
			if (q[i - 1] + 1 == q[i] - 1)
			{
				p.push_back(A[q[i - 1] + 1]);
			}
			else if (total>0 && q[i - 1] + 1 != q[i] - 1)
			{
				p.push_back(total);
				total = 1;
			}
			else if (total < 0 && q[i - 1] + 1 != q[i] - 1)
			{
				max = total;
				temp = total;
				for (k = q[i - 1] + 1; k < q[i] - 1; k++)
				{
					total = total / A[k];
					if (total>max)
						max = total;
				}
				total = temp;
				for (k = q[i] - 1; k > q[i - 1] + 1; k--)
				{
					total = total / A[k];
					if (total > max)
						max = total;
				}
				p.push_back(max);
				total = 1;
			}
		}
		if (q[q.size() - 1] + 1 < n)
		{
			total = 1;
			for (j = q[q.size() - 1] + 1; j < n; j++)	//q[q.size-1]+1～n-1之間的最大值取出並存入p中
				total *= A[j];
			if (total > 0)
			{
				p.push_back(total);
				total = 1;
			}
			else
			{
				max = total;
				temp = total;
				for (k = q[q.size() - 1] + 1; k < n - 1; k++)
				{
					total = total / A[k];
					if (total>max)
						max = total;
				}
				total = temp;
				for (k = n - 1; k > q[q.size() - 1] + 1; k--)
				{
					total = total / A[k];
					if (total > max)
						max = total;
				}
				p.push_back(max);
				total = 1;
			}
		}
		max = 0;									//取出p中的最大值
		for (k = 0; k < p.size(); k++)
		{
			if (p[k]>max)
				max = p[k];
		}
		if (max > 0)
			return max;
		else
			return 0;
	}
	else if (total < 0)								//total<0 的情況 運用算法求出最大字串product
	{
		temp = total;
		max = total;
		for (j = 0; j < n-1; j++)
		{
			total = total / A[j];
			if (total>max)
				max = total;
		}
		total = temp;
		for (j = n - 1; j>0; j--)
		{
			total = total / A[j];
			if (total > max)
				max = total;
		}
		return max;
	}
}