Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

http://www.lintcode.com/en/problem/maximum-product-subarray/

Discussion

跟Maximum Subarray问题不同之处在于两个负数相乘就变成正的了，本来是-60不考虑的，下次再来个-1，如果-60已经丢了的话最大值就找不到了，所有需要两个local， localmin, localmax， 乘以当前元素以后得到当前curmax curmin，最后localmax localmin是从curmax curmin nums[i]三个里面选出来的。

Solution

class Solution {
public:
    /**
     * @param nums: a vector of integers
     * @return: an integer
     */
    int maxProduct(vector<int>& nums) {
        // write your code here
        if(nums.size() == 0) return 0;
        int result = nums[0];
        int localmax = nums[0], localmin = nums[0];
        for(int i=1; i<nums.size(); i++) {
            int curmax = localmax*nums[i];
            int curmin = localmin*nums[i];
            localmax = max(nums[i], max(curmax, curmin));
            localmin = min(nums[i], min(curmax, curmin));
            if(localmax > result) result = localmax;
        }
        return result;
    }
};