class Solution {
public:
    int maxProduct(vector<int>& nums) {

        int tmp = 1;
        int maxProdResult = INT_MIN;
        int len = nums.size();

        if (len == 1)
            return nums[0];

        for(int i = 0; i < len; i++) {          //start position

            tmp = nums[i];

            if (nums[i] > maxProdResult)
               maxProdResult = nums[i];

            for(int j = i+1; j < len; j++) {    //end position
                tmp *= nums[j];

                if (tmp > maxProdResult)
                    maxProdResult = tmp;
            }
        }

        return maxProdResult;
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums) {

        int len = nums.size();

        if (len == 0)
            return 0;

        if (len == 1)
            return 1;

        vector<int> DpMax;
        vector<int> DpMin;

        DpMax[0] = nums[0];
        DpMin[0] = nums[0];

        for ( int i = 0; i < len; i++) {
            if (nums[i] > 0){
                DpMax[i] = max(nums[i], DpMax[i-1] * nums[i]);
                DpMin[i] = min(nums[i], DpMax[i-1] * nums[i]);
            }
            else {
                DpMax[i] = max(nums[i], DpMin[i-1] * nums[i]);
                DpMin[i] = min(nums[i], DpMax[i-1] * nums[i]);
            }
        }

        return *max_element(DpMax.begin(), DpMax.end());
    }
};