这道花了本人近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; } }