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 [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

1. Fist we assume there is no zero in the nums[]. The answer must be nums[0] nums[1] .... nums[i] OR nums[j] *nums[j+1] nums[n - 1]. 

2. Then when we have zero in the nums[] (assum nums[k] == 0). We could see nums[0],nums[1]...nums[k - 1 ] As An Array and nums[k + 1] nums[k + 2]...nums[n-1] is another.

the key point of this problem is: there are only two patterns.
One is "aBcD", and the other is "aBcDe", where I use lowercase to denote a negative number, and use upper case to denote a positive number.
For the first pattern, the maximum product would be "aBcD"; and for the second pattern, the maximum product would be "max (aBcD, BcDe)". So above solution code is very elegant and efficient.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)  return 0;

        int fromFront = 1;
        int fromBack = 1;
        int res = INT_MIN;

        for(int i = 0; i < n; i++){
            fromFront *= nums[i];
            fromBack *= nums[n - 1 - i];

            res = max(res, max(fromFront, fromBack));

            fromFront = fromFront == 0?1:fromFront;
            fromBack = fromBack == 0?1:fromBack;
        }
        return res;
    }
};

另一种解法

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty())    return 0;

        int maxHerePre = nums[0];
        int minHerePre = nums[0];
        int maxSofar = nums[0];

        int maxHere, minHere;

        for(int i = 1; i < nums.size(); i++){
            maxHere = max(max(maxHerePre * nums[i], minHerePre*nums[i]), nums[i]);
            minHere = min(min(maxHerePre * nums[i], minHerePre*nums[i]),nums[i]);

            maxSofar = max(maxSofar, maxHere);

            maxHerePre = maxHere;
            minHerePre = minHere;
        }
        return maxSofar;
    }
};