Maximum Subarray Product Volume

It is very similar to Subarray Max Sum and much simpler than Subarray Max Product which allows negative number . The basic ideas are the same: currentMax = max(a[i], some_operation(currentMax, a[i]))

.

For each item, we have 2 options: put it in a sequential submachine, 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);
}

      

        
        
        
      

    

for each array and update max and min every time. min * A [i] possible max. and the code here, passed to 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;
    }
}

      

        
        
        
      

    

My Java solution that covers the case where the input array can contain negative numbers:

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;
    }
}

      

        
        
        
      

    

Taken at Leetcode .

Update . The following (fairly simple) optimization is for finding min and max among 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 Leetcode .

This made me think if I could 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;
    }
}

      

        
        
        
      

    

Taken at Leetcode .

Here's the Ruby implementation:

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

      

        
        
        
      

    

Example:

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

      

        
        
        
      

    

Output:

180