题目链接：点击打开链接
题目信息：
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,⑵,4],
the contiguous subarray [2,3] has the largest product = 6.
解题思路： 习惯最小字符串的和，突然来了1道最小字符串的乘积，也挺成心思。
分两种情况讨论：字符数组中无0，有0。两种情况。
（1）字符数组中无0
字符数组中，其实就两种，偶数个负数，奇数个负数。
1，偶数个负数，例如 [ ⑴ 2 3 ⑷ 5]，很明显最大的字符串就是全部。
2，奇数个负数，例如 [⑵ 2 5 ⑷ ⑶], 最大的字符串就是，第1个负数后面的子串[2 5 ⑷ ⑶].
所以综上所述，最大字符串就只有两种情况，1种是全部字符串，1种是第1个负数后面的字符串。所以只要存储这两种情况下的值， 再进行比较就可以得出最后结果。
（2）字符串中有0
前面能实现，我们就把0后的数组，当做1个新的数组就可以实现了。例如[5 6 ⑸ 0 2 3 8 9 ⑸],就能够把0后面的数组看成新数组就行
[2 3 8 9 ⑸];
代码：
public:
int maxProduct(int A[], int n) {
int preNum1 = 1; //Remember all the Numbers
int preNum2 = 1; //Remember all the Behind Numbers of first negative
bool start2;
int answers ;
if(n == 0) return 0;
if(n > 0) answers = A[0];
int negSum = 0;
for(size_t i = 0; i != n;i++) {
preNum1 *= A[i];
//cout<<"preNum1="<<preNum1<<endl;
answers = (preNum1 > answers? preNum1:answers);
if(start2 == true) {
preNum2 *= A[i];
//cout<<"preNum2="<<preNum2<<endl;
answers = (preNum2 > answers? preNum2:answers);
}
if(A[i] < 0) {
negSum ++;
}
if(negSum == 1 && start2 == false) {
start2 = true;
preNum2 = 1;
}
if(A[i] == 0) {
answers = (answers > 0) ? answers : 0;
preNum1 = 1;
preNum2 = 1;
negSum = 0;
start2 = false;
}
}
return answers;
}
};
转载请注明作者：vanish_dust
波比源码 » LeetCode-Maximum Product Subarray
