Maximum Product Subarray

Problem

Maximum Product Subarray

Intuition

1. To make the product larger, we have to add more positive numbers into answer or more even number of negtive numbers into answer. So, with the greedy strategy, we can iterate the array. If counters positive, it’s added immediately. If counters negtive, we can check if there is more negtive numbers in right of current position. If counters zero, we initialize the current state. In this greedy way, we have to iterate the array one more time in reverse order.

2. Besides that, we can also use Dynamic Programming to solve it. DpMax[i] means currently the largest product, including the i-th element and DpMin[i] means the smallest product, including the i-th element. And, more important, the transition is like DpMax[i] = max(DpMax[i - 1] * nums[i], DpMin[i - 1] * nums[i], nums[i]) and in the same way, DpMin[i] = min(DpMax[i - 1] * nums[i], DpMin[i - 1] * nums[i], nums[i]). Lastly, we can get the final answer.

Code

// greedy way
class Solution {
    public int maxProduct(int[] nums) {
        int N = nums.length;
        if(N == 1) {
            return nums[0];
        }
        int ans = 0, curAns = 1;
        for(int i = 0; i < N; i ++){
            if(nums[i] == 0){
                curAns = 1;
            } else {
                curAns *= nums[i];
                ans = Math.max(ans, curAns);
            }
        }
        
        curAns = 1;
        for(int i = N - 1; i >= 0; i --){
            if(nums[i] == 0){
                curAns = 1;
            } else {
                curAns *= nums[i];
                ans = Math.max(ans, curAns);
            }
        }
        return ans;
    }
}

// DP
class Solution {
    public int maxProduct(int[] nums) {
        int N = nums.length;
        int[] max = new int[N], min = new int[N];
        max[0] = nums[0];
        min[0] = nums[0];
        int ans = nums[0];
        for(int i = 1; i < N; i ++){
            max[i] = Math.max(max[i - 1] * nums[i], min[i - 1] * nums[i]);
            max[i] = Math.max(max[i], nums[i]);
            min[i] = Math.min(max[i - 1] * nums[i], min[i - 1] * nums[i]);
            min[i] = Math.min(min[i], nums[i]);
            ans = Math.max(ans, max[i]);
        }
        return ans;
    }
}