DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Max product subarray

Max product subarray

tc:O(n), sc:O(1)

class Solution {
    public int maxProduct(int[] nums) {
        // we will move left to right to find the maximum product:prefix:
        //we will move from right to left to find the maximum product: suffix 
        // and max(prefix,suffix ) will be the answer
        /// if we incounter 0 in the array we will make either suffix or prefix 1 that way we will make sure that we have 
        ///avoided 0 in consideration else it will lead to 0 product which we dont want
        int max = Integer.MIN_VALUE;
        int prefix= 1;
        int suffix=1;
        for(int i =0;i<nums.length;i++){
            if(prefix ==0) prefix = 1;
            if(suffix ==0) suffix = 1;
            prefix = prefix * nums[i];
            suffix = suffix * nums[nums.length-1-i];
            max = Integer.max(max, Integer.max(prefix, suffix));
        }
        return max;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)