Leetcode 152: 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.

这题跟maximum sum subarray的思路一样，但是由于乘法不能直接根据后面的数对之前的数进行处理，因为可能前面一个很小的负数，乘以下一个负数会变成最大值，所以需要有一个local的最小值。 这题是动态规划的思想，动态规划+local_max+global_max, global_max是全局最大值，local_max是必须包含nums[i]在内的最大值，local_max的递推式： local_max = max(max(local_max, nums[i]), f(nums[i]))); global_max = max(global_max,local_max):这样就可以包括所有可能取值的情况了。
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //sanity chek
        if (nums.size() == 0) return 0;
        int max_local = nums[0];
        int min_local = nums[0];
        int global = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int tmp = max_len;
            max_local = max(max(nums[i], nums[i]*max_len), nums[i]*min_len);
            min_local= min(min(nums[i], nums[i]*tmp),nums[i]*min_len);
            global = max(global, max_local);
        }
        return global;
    }
};