题目:
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4]
,
the contiguous subarray [2,3]
has the largest product = 6
.
解题:
因为0比较影响结果,对0进行特判,凡是出现0的地方,重新计算。
每次计算的方式是计算le~ri之间的最大值,从左边往右记录le~x的积和从右往左扫记录x~ri的积,取个最大值就好了
代码:
class Solution { public: int maxProduct(int A[], int n) { if(!n) return 0; int le = 0, ans = A[0]; memset(sumL, 0, sizeof(int) * n); memset(sumR, 0, sizeof(int) * n); for(int i = 0; i < n; i ++) { if(!A[i]) { ans = max(ans, gao(le, i - 1, A)); le = i + 1; ans = max(ans, 0); } } ans = max(ans, gao(le, n - 1, A)); return ans; } private: static const int SIZE = 100000; int sumL[SIZE], sumR[SIZE]; int gao(int le, int ri, int A[]) { if(ri < le) return INT_MIN; //之前返回A[le],但le可能超过边界n,导致出错 sumL[le] = A[le], sumR[ri] = A[ri]; for(int i = le + 1; i <= ri; i ++) sumL[i] = sumL[i - 1] * A[i]; for(int i = ri - 1; i >= le; i --) sumR[i] = sumR[i + 1] * A[i]; if(sumL[ri] > 0) return sumL[ri]; int sum = A[le]; for(int i = le; i <= ri; i ++) { if(A[i] <= 0) { if(i != le) sum = max(sum, sumL[i - 1]); if(i != ri) sum = max(sum, sumR[i + 1]); } } return sum; } };