Maximum Product Subarray

• https://leetcode.com/problems/maximum-product-subarray/

When iterating the array, each element has two possibilities: positive number or negative number. We need to track a minimum value, so that when a negative number is given, it can also find the maximum value

/*
 * Time complexity O(N), space complexity O(N).
 */
public int maxProduct(int[] nums) {
    int[] minSum = new int[nums.length];
    int[] maxSum = new int[nums.length];
    minSum[0] = nums[0];
    maxSum[0] = nums[0]; 
    int max = nums[0];

    for (int i = 1; i < nums.length; i++) {
        maxSum[i] = Math.max(nums[i], Math.max(nums[i] * maxSum[i-1], nums[i] * minSum[i-1]));
        minSum[i] = Math.min(nums[i], Math.min(nums[i] * minSum[i-1], nums[i] * maxSum[i-1]));
        max = Math.max(Math.max(max, maxSum[i]), minSum[i]);
    }

    return max;    
}