LeetCode-Maximum Product Subarray
|
题目链接：点击打开链接 题目信息： Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example,given the array 解题思路： 习惯最小字符串的和，突然来了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 ⑸]; 代码： class Solution {
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 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |