Leetcode-152- product maximum subarray

# LeetCode-152- Product maximum subarray

Give you an array of integers nums , Please find the continuous subarray with the largest product in the array （ The subarray contains at least one number ）, And returns the product of the subarray .

Example 1：

 Input : [2,3,-2,4]
 Output : 6
 explain :  Subarray  [2,3]  There is a maximum product  6.

Copy

Example 2：

 Input : [-2,0,-1]
 Output : 0
 explain :  The result can't be  2,  because  [-2,-1]  It's not a subarray .

Copy

# Their thinking

Method 1、 Dynamic programming ：

When traversing the array, constantly calculate the current maximum value

At the same time, it is also necessary to record the previous minimum value , When traversing to nums[i] When it's negative

Maximum * negative ： Will cause the maximum value to become the minimum

minimum value * negative ： It will cause the minimum value to become the maximum

Therefore, it is necessary to maintain the current maximum value and the current minimum value

The maximum value can be determined by curMax = Math.max(curMax*nums[i],nums[i]); Calculation

The minimum value can be determined by curMin = Math.min(curMin*nums[i],nums[i]); Calculation

The maximum and minimum values are interchangeable , The result is wrong

In that case, when you encounter negative numbers nums[i] When , Swap the maximum and minimum values in advance , The original maximum and minimum values can be maintained

A better solution comes from https://leetcode-cn.com/problems/maximum-product-subarray/solution/dpfang-fa-xiang-jie-by-yang-cong-12/

# Java Code

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE;
        int curMax = 1;
        int curMin = 1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]<0){
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }
            curMax = Math.max(curMax*nums[i],nums[i]);
            curMin = Math.min(curMin*nums[i],nums[i]);
            max = Math.max(max,curMax);
        }
        return max;
    }
}

Copy

dp Array version

# Java Code

class Solution {
    public int maxProduct(int[] nums) {
        int[] dp_max = new int[nums.length+1];
        int[] dp_min = new int[nums.length+1];
        if(nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        //  Because there are negative numbers , So you need to maintain two arrays 
        // dp_max[i]  Refers to the first  i  Number ending   Product maximum   A continuous subsequence of 
        // dp_min[i]  Refers to the first  i  Number ending   The product is the smallest   A continuous subsequence of 
        dp_max[0] = 1;
        dp_min[0] = 1;
        for (int i = 1;i <= nums.length;i++){
            //  If the number of arrays is negative , It will lead to  max  become  min,min  become  max
            //  So we need to exchange dp 
            if(nums[i-1] < 0){
                int temp = dp_min[i-1];
                dp_min[i-1] = dp_max[i-1];
                dp_max[i-1] = temp;
            }
            dp_min[i] = Math.min(nums[i-1],dp_min[i-1]*nums[i-1]);
            dp_max[i] = Math.max(nums[i-1],dp_max[i-1]*nums[i-1]);
            max = Math.max(max,dp_max[i]);
        }
        return max;
    }
}

Copy