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.

分析

2个负数相乘可以得到最大值，需要存储当前最小的数。

*  second method: DP: curMax is the max of product contains the current element;
 *        since element can be negetive, maximum value can be obtain by product of two negtive numbers;
 *        we also need to store the current minimum product;
 *        when go to next element;
 *        if nums[i] < 0; curMax = Math.max(nums[i], nums[i]* curMin);
 *                        curMin = Math.min(nums[i], nums[i]* curMax);
 *                        (can swap curMax and curMin, and conbine the expression for those two conditions.
 *        else:           curMax = Math.max(nums[i], nums[i]* curMax);
 *                        curMin = Math.min(nums[i], nums[i]* curMin);

可以直接交换curMin和curMax

当前状态需要考虑前面的几步，而无法从前一个数直接决定：比如前面数可能取了负数成了最小，但遇到下一个负数成了最大，所以前数需要保留负数态。如果只考虑一个状态，前数会直接取正数，导致得不到最大。

所以这里设置两个全局变量以便考虑前面几个的状态，同时注意curMax和curMin都必须包含当前数，意味着下一步使用这俩变量时候，保证了数组的连续性。

答案

public class Solution {
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    public int maxProduct(int[] nums) {
        // write your code here

        if(nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;

        int max = nums[0], curMin = nums[0], curMax = nums[0];
        for(int i = 1; i < n; 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;

    }
}

python

负负得正，所以2个数组，一个存最大一个存最小

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] + [i for i in nums]
        mdp = [1] + [i for i in nums]
        res = float('-inf')
        for i in range(1,n+1):
            dp[i] = max(dp[i],dp[i-1]*nums[i-1],mdp[i-1]*nums[i-1])
            mdp[i] = min(mdp[i],mdp[i-1]*nums[i-1],dp[i-1]*nums[i-1])
            res = max(res,dp[i])
        return res

因为只和前面状态min,max相关，并且当前态就能比较出res，只要设置这3个变量即可

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        
        mn,mx,res = 1,1,float('-inf')
        for i in nums:
            mn,mx = min(i, mn*i,mx*i),max(i,mx*i,mn*i)
            res = max(mn,mx,res)
        return res