Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

其实不用考虑太多情况，只需要比较dp最大 dp最小乘以当前值 和当前值比较就好了

时间复杂度 o(n).空间复杂度 o(n)

class Solution {
    public int maxProduct(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        
       int[] dpMax = new int[nums.length];
       int[] dpMin = new int[nums.length];
        
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        
        int res = nums[0];
        
        for(int i = 1; i < nums.length ;i++){
            dpMax[i] = Math.max(Math.max(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i]),nums[i]);
             dpMin[i] = Math.min(Math.min(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i]),nums[i]);
               res = Math.max(dpMax[i],res);
        }
        
        
        return res;
    }
}

时间复杂度 o(n),空间复杂度 o(1)

class Solution {
    public int maxProduct(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        int min = nums[0];
        int max = nums[0];
        int res = nums[0];
        int prevMax = max, prevMin = min;
        
        for(int i = 1; i < nums.length;i++){
            max = Math.max(Math.max(prevMin*nums[i],prevMax*nums[i]),nums[i]);
            min = Math.min(Math.min(prevMin*nums[i],prevMax*nums[i]),nums[i]);
            res = Math.max(res,max);
            prevMax = max; 
            prevMin = min;
        }
        
        return res;
    }
}

找到最大乘积数组

class Solution {
    public int maxProduct(int[] nums) {
         //arguement check
       if(nums == null || nums.length == 0) return 0;

       //help variable and array define

        int max = nums[0];
        int min = nums[0];

        int res = nums[0];
        
        int start = 0, end = 0;
        int[] r = new int[2];
       //go through nums array
        for(int i = 1; i < nums.length;i++){
            int tmpMax = max, tmpMin = min;

            max = Math.max(  Math.max(  tmpMax*nums[i], tmpMin*nums[i] ), nums[i]);
            
            min = Math.min(  Math.min(  tmpMax*nums[i], tmpMin*nums[i] ), nums[i]);
            
            //res = Math.max(res,max);
            
            if(max < tmpMax){
                start = i;
                end =i;
            }
            
            else if(max >= tmpMax){
                end++;
            }
            
            if(max > res){
                res = max;
                r[0] = start;
                r[1] = end;
            }
        }
        System.out.println(r[0] + " "+ r[1]);
        return res;

        //time o(n), space o(1);
    }
}