Maximum Product Subarray

Question

I have an array of n positive real numbers

And I have to find out the Maximum Product Subarray for this given array.

How to implement DP Solution for the problem ?

Explain in detail the DP formulation of the solution.

Answer 1

Works perfect for me in java. All test case passed. RunTime 1ms.

public int maxProduct(int[] nums) {

    int curr_max_prod= nums[0];

    int curr_min_prod= nums[0];

    int prev_max= nums[0];

    int prev_min = nums[0];
    int ans= nums[0];

    for(int i=1;i<nums.length;i++){
        int k= Math.max(nums[i]*prev_max, nums[i]*prev_min);
        curr_max_prod=Math.max(k, nums[i]);

        int h =Math.min(nums[i]*prev_max, nums[i]*prev_min);

        curr_min_prod= Math.min(h, nums[i]);

        ans=Math.max(ans,curr_max_prod);
        prev_max=curr_max_prod;
        prev_min=curr_min_prod;


    }
    return ans;


}

Answer 2

Example explanation:

input = [ 2, 3, -2, 4 ]

product_left_to_right = input = [ 2, 3, -2, 4 ]

product_right_to_left = input[::-1] = [ 4, -2, 3, 2 ]

1st iteration:

6 = 3 * 2 product_left_to_right = [ 2, 6, -2, 4 ]

-8 = -2 * 4 product_right_to_left = [ 4, -8, 3, 2 ]

2nd iteration:

-12 = -2 * 6 product_left_to_right = [ 2, 6, -12, 4 ]

-24 = 3 * -8 product_right_to_left = [ 4, -8, -24, 2 ]

3rd iteration:

-48 = 4 * -12 product_left_to_right = [ 2, 6, -12, -48 ]

-48 = 2 * -24 product_right_to_left = [ 4, -8, -24, -48 ]

comparison of max:

max of product_left_to_right = [ 2, 6, -12, -48 ] = 6

max of product_right_to_left = [ 4, -8, -24, -48 ] = 4

max of ( 6, 4 ) = 6

return 6

def maxProduct(self, nums: List[int]) -> int:
        l = len(nums)
        nums_l=nums //product_left_to_right 
        nums_r = nums[::-1] //product_right_to_left
        for i in range(1,l,1):
            nums_l[i] *= (nums_l[i-1] or 1) //if meets 0 then restart in-place by itself.
            nums_r[i] *= (nums_r[i-1] or 1) 
        return max(max(nums_l), max(nums_r))

Answer 3

Here is an implementation is Ruby:

def max_subarray_product(arr)
  maxi = 1
  mini = 1
  result = 0

  arr.each do |i|
    temp_max =  maxi > 1 ? maxi : 1
    if (i > 0)
      maxi = temp_max*i
      mini *= i
    else
      maxi = mini*i
      mini = temp_max*i
    end
    result = maxi > result ? maxi : result
  end
  result
end

For Example:

a = [6, -3, -10, 0, 2]
puts maxsubarrayproduct(a)

Output:

180

Answer 4

Since numbers are all positive, multiple them all.

Answer 5

My Java solution which covers the case where the input array may contain negative numbers also:

public class MaximumProductSubarraySolver
{
    public int maxProduct(int[] a)
    {
        int max_so_far = a[0];
        int max_ending_here = a[0];
        int min_ending_here = a[0];
        for (int i = 1; i < a.length; i++)
        {
            int max1 = max_ending_here * a[i];
            int min1 = min_ending_here * a[i];

            max_ending_here = Math.max(a[i], Math.max(min1, max1));
            min_ending_here = Math.min(a[i], Math.min(min1, max1));

            max_so_far  = Math.max(max_so_far, max_ending_here);
        }
        return max_so_far;
    }
}

Accepted on Leetcode.

Update: The following (quite simple) optimization for finding min and max among the three numbers a[i], max1, and min1 gives a huge performance jump:

public class MaximumProductSubarraySolver {
    public int maxProduct(int[] a) {
        int max_so_far, max_ending_here, min_ending_here;
        max_so_far = max_ending_here = min_ending_here = a[0];

        for (int i = 1; i < a.length; i++)
        {
            int max1 = max_ending_here * a[i];
            int min1 = min_ending_here * a[i];

            // find min and max among a[i], max1, and min1
            // max_ending_here = max(a[i], max1, min1)
            // min_ending_here = min(a[i], max1, min1)
            if(a[i] >= min1)
            {
                if(min1 >= max1)
                {
                    max_ending_here = a[i];
                    min_ending_here = max1;
                }
                else
                {
                    // a[i] >= min1
                    // max1 > min1
                    min_ending_here = min1;
                    max_ending_here = a[i] >= max1 ? a[i] : max1;
                }
            }
            else
            {
                // a[i] < min1
                if(min1 <= max1)
                {
                    max_ending_here = max1;
                    min_ending_here = a[i];
                }
                else
                {
                    //a[i] < min1
                    //max1 < min1
                    max_ending_here = min1;
                    min_ending_here = a[i] <= max1 ? a[i] : max1;
                }
            }

            if(max_ending_here > max_so_far)
            {
                max_so_far  = max_ending_here;
            }
        }

        return max_so_far;
    }
}

Optimized code on Leetcode.

This lead to me thinking if I can simplify this code. This is what I came up with:

public class MaximumProductSubarraySolver {
    public int maxProduct(int[] a) {
        int max_so_far, max_ending_here, min_ending_here;
        max_so_far = max_ending_here = min_ending_here = a[0];

        for (int i = 1; i < a.length; i++)
        {
            if(a[i] < 0)
            {
                // when a[I] < 0
                //     max * a[i] will become min
                //     min * a[i] will become max
                int t = max_ending_here;
                max_ending_here = min_ending_here;
                min_ending_here = t;
            }

            int max1 = max_ending_here * a[i];
            int min1 = min_ending_here * a[i];

            max_ending_here = a[i] > max1 ? a[i] : max1;
            min_ending_here = a[i] < min1 ? a[i] : min1;

            if(max_ending_here > max_so_far)
            {
                max_so_far  = max_ending_here;
            }
        }

        return max_so_far;
    }
}

Accepted on Leetcode.

Answer 6

My code that passed Leetcode OJ:

class Solution {
public:
    int maxProduct(int A[], int n) {
        if (n==0) return 0;

        int maxi = 1, mini = 1;
        int out = INT_MIN;

        for (int i=0;i<n;i++) {
            int oldmaxi = max(maxi,1);
            if (A[i] > 0) {
                maxi = oldmaxi*A[i];
                mini *= A[i];
            } else {
                maxi = mini*A[i];
                mini = oldmaxi*A[i];
            }
            out = max(out,maxi);
        }

        return out;
    }
};

Explanations could be found here: http://changhaz.wordpress.com/2014/09/23/leetcode-maximum-product-subarray/

Answer 7

for each the array, and update the max and min every time. min*A[i] maybe the max. and code is here, passed in leetcode:

public class Solution {
    public int maxProduct(int[] A) {
        int max = A[0];
        int min = A[0];
        int maxProduct = A[0];

        for(int i = 1; i < A.length; i ++) {
            int temp = max;
            max = Math.max(Math.max(A[i], max*A[i]), min*A[i]);
            min = Math.min(Math.min(A[i], min*A[i]), temp*A[i]);
            if(max > maxProduct)
                maxProduct = max;
        }
        return maxProduct;
    }
}

Answer 8

Since the solution for maximal sum is known, you can

• compute log of each array's item into another array
• apply the known algorithm to the new array
• exp of the result is the answer.

(But you can just trivially adjust the existing algorithm, which is already mentioned in @nevets's answer. Replace the constant 0 (which is additive neutral element) with 1.)

Answer 9

It's very similar to Maximum Sum of Subarray problem and a lot easier than Maximum Product of Subarray which allows negative number. The core ideas are the same: currentMax = max(a[i], some_operation(currentMax, a[i])).

For each element, we have 2 options: put it inside a consecutive subarray, or start a new subarray with it.

double currentMax = a[0];

for (int i = 1; i < size; i++)
{
     currentMax = max(a[i], currentMax * a[i]);
     best = max(best, currentMax);
}