Maximum Product Subarray

Question

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.

LeetCodeleetcode.com/problems/maximum-product-subarray

Solution

/*
@param:
@return:
Algorithm: 因为存在负数的情况，所以product可能为两个最小负数相乘
保留两个int[] max, min，来分别保留之前状态的最大值与最小值。
*/
public int maxProduct(int[] nums) {
    if ( nums.length == 0 ) return 0;
    int len = nums.length;
    int[] max = new int[len];
    int[] min = new int[len];
    
    max[0] = nums[0]; 
    min[0] = nums[0];
    int result = nums[0];
    for ( int i = 1; i < nums.length; i++ ){
        max[i] = Math.max(nums[i], Math.max(max[i-1]*nums[i], min[i-1]*nums[i]));
        min[i] = Math.min(nums[i], Math.min(max[i-1]*nums[i], min[i-1]*nums[i]));
        result = Math.max(result, Math.max(max[i], min[i]));
    }
    return result;
}