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.

【analyze】

1.动态规划的算法，与Maximum Subarray类似

2.不过需要考虑两个负数相乘又会成为正数

3.设置局部最大值（正），局部最小值（负）和全局最大值

【算法】

public class Solution {
    public int maxProduct(int[] nums) {
        if(nums==null||nums.length==0)
            return 0;
        if(nums.length==1)
            return nums[0];
        int local_max=nums[0];
        int local_min=nums[0];
        int global=nums[0];
        for(int i=1;i<nums.length;i++) {
            int temp=local_max;
            local_max=Math.max(Math.max(nums[i]*local_max,nums[i]),nums[i]*local_min);   //local_max*nums[i],num[i]和num[i]*local_min的比较
            local_min=Math.min(Math.min(nums[i]*local_min,nums[i]),nums[i]*temp);
            global=Math.max(local_max,global);
        }
        return global;
    }
}