题目来源
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.
最简单直接的方法当然是把所有可能都算一遍，复杂度是O(n^2)。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int res = INT_MIN;
for (int i=0; i<n; i++) {
int pd = 1;
for (int j=i; j<n; j++) {
pd *= nums[j];
res = max(res, pd);
}
}
return res;
}
};
但是显然不可能那么简单，结果只有一个，那就是TLE！
好吧，好好想想应该怎么做呢？想啊想啊想不出来，然后我又看答案去了…
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int r = nums[0];
for (int i=1, imin = r, imax = r; i<n; i++) {
if (nums[i] < 0)
swap(imin, imax);
imax = max(nums[i], imax * nums[i]);
imin = min(nums[i], imin * nums[i]);
r = max(r, imax);
}
return r;
}
};
看完真是不能自已，这尼玛，大神们都什么脑子啊！
对于每个元素，有两种可能，一个是重新开始，一个是乘上以前的。
从前往后遍历，imin和imax存储以当前元素为结尾的最大值和最小值，假如下一个元素小于0，则调换一下两个变量值，因为越大的数乘以负数就越小。
感觉有点抽象，得好好理解一下！
