Maximum Product Subarray

Chaitra Rai

·

Follow

2 min read

·

Nov 8, 2021

--

Listen

Share

Given an array that contains n integers that could be positive, negative, or zero, return the product returned by the subarray with the maximum product (Full Question)

• The problem is similar to the Maximum sum Subarray Problem
• Brute force would be to iterate through the array with two pointers i and j; where i goes from 0 to n and j from i+1 to n
• For each iteration, we check if the product is the maximum encountered yet with a result and mul variable via comparison
• This algorithm has a time complexity of O(n²) and O(1) space complexity

long maxProduct(int[] arr, int n) {
        long result=arr[0];
        long mul=0;
        for(int i=0;i<n;i++){
            mul=arr[i];
            for(int j=i+1;j<n;j++){
                mul*=arr[j];
                result=Math.max(result, mul);
            }
        }
        result=Math.max(result, mul);
        //check for last element at n-1
        return result;
    }

• We can avoid iterating the array n² times by splitting the iteration into 2 parts; once we iterate forward and then next backward
• We find the maximum product while iterating forward and backward each and compare them to get the maximum among both ((O(n)+O(n)))
• We keep a boolean variable isZero to have a check on the zero products
• This algorithm has a time complexity of O(n) and O(1) space complexity

long maxProduct(int[] arr, int n) {
        long result=1;
        long max_forward=Integer.MIN_VALUE;
        long max_backward=Integer.MIN_VALUE;
        boolean isZero=false;
        for(int i=0;i<n;i++){
            result=result*arr[i];
            if(result==0){
                isZero=true;
                result=1;
                continue;
            }
            if(max_forward<result){
                max_forward=result;
            }
        }
        result=1;
        for(int i=n-1;i>=0;i--){
            result=result*arr[i];
            if(result==0){
                isZero=true;
                result=1;
                continue;
            }
            if(max_backward<result){
                max_backward=result;
            }
        }
        result=Math.max(max_forward, max_backward);
        //check for last element at n-1
        return result;
    }

• Another way is to not iterate the array twice but to keep a variable minValue to keep a check on the product turning negative and swap with the present maxValue
• This algorithm has a time complexity of O(n) and O(1) space complexity

long maxProduct(int[] arr, int n) {
        long maxValue=arr[0];
        long maxProduct=arr[0];
        long temp=0;
        long minValue=arr[0];
        for(int i=1; i<n; i++){
            if(arr[i]<0){
                temp=maxValue;
                maxValue=minValue;
                minValue=temp;
            }
            maxValue=Math.max(arr[i], maxValue*arr[i]);
            minValue=Math.min(arr[i], minValue*arr[i]);
            maxProduct=Math.max(maxProduct,maxValue);
        }
        return maxProduct;
    }