Maximum Product Subarray

lc 152

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.

这个题因为是负数，所以需要存一个local最小，和一个local最大，以lc 53 Maximum Subarrayglobal的数组。 注意看一下lc 53 Maximum Subarray

public class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] llocal = new int[n];
        int[] hlocal = new int[n];
        int[] global = new int[n];

        llocal[0] = nums[0];
        hlocal[0] = nums[0];
        global[0] = nums[0]; 

        for(int i = 1; i < n; i++ ){
            llocal[i] = Math.min(Math.min(llocal[i-1] *nums[i], hlocal[i-1] * nums[i] ), nums[i]);
            hlocal[i] = Math.max(Math.max(llocal[i-1] *nums[i], hlocal[i-1] * nums[i] ), nums[i]);
            global[i] = Math.max(Math.max(llocal[i],hlocal[i]), global[i-1]);
        }
        return global[n-1];
    }
}