Find the contiguous sequence with the largest product in an integer array

I have come up with the code below but that doesn't satisfy all cases, e.g.:

1. Array consisting all 0's

2. Array having negative values(it's bit tricky since it's about finding product as two negative ints give positive value)

   public static int LargestProduct(int[] arr)
   开发者_开发百科{   
       //returning arr[0] if it has only one element
       if (arr.Length == 1) return arr[0];
   
       int product = 1;
       int maxProduct = Int32.MinValue;
   
       for (int i = 0; i < arr.Length; i++)
       {
           //this block store the largest product so far when it finds 0 
           if (arr[i] == 0)
           {
               if (maxProduct < product)
               {
                   maxProduct = product;
               }
               product = 1;
           }
           else 
           {
               product *= arr[i];
           }
       }
       if (maxProduct > product)
           return maxProduct;
       else
           return product;
   }
   

How can I incorporate the above cases/correct the code. Please suggest.

I am basing my answer on the assumption that if you have more than 1 element in the array, you would want to multiply at least 2 contiguous integers for checking the output, i.e. in array of {-1, 15}, the output that you want is -15 and not 15).

The problem that we need to solve is to look at all possible multiplication combinations and find out the max product out of them.

The total number of products in an array of n integers would be nC2 i.e. if there are 2 elements, then the total multiplication combinations would be 1, for 3, it would be 3, for 4, it would be 6 and so on.

For each number that we have in the incoming array, it has to multiply with all the multiplications that we did with the last element and keep the max product till now and if we do it for all the elements, at the end we would be left with the maximum product.

This should work for negatives and zeros.

    public static long LargestProduct(int[] arr)
    {
        if (arr.Length == 1)
            return arr[0];

        int lastNumber = 1;
        List<long> latestProducts = new List<long>();
        long maxProduct = Int64.MinValue;
        for (int i = 0; i < arr.Length; i++)
        {
            var item = arr[i];
            var latest = lastNumber * item;
            var temp = new long[latestProducts.Count];
            latestProducts.CopyTo(temp);
            latestProducts.Clear();
            foreach (var p in temp)
            {
                var product = p * item;
                if (product > maxProduct)
                    maxProduct = product;
                latestProducts.Add(product);
            }
            if (i != 0)
            {
                if (latest > maxProduct)
                    maxProduct = latest;
                latestProducts.Add(latest);
            }
            lastNumber = item;
        }
        return maxProduct;
    }

If you want the maximum product to also incorporate the single element present in the array i.e. {-1, 15} should written 15, then you can compare the max product with the element of the array being processed and that should give you the max product if the single element is the max number. This can be achieved by adding the following code inside the for loop at the end.

if (item > maxProduct)
    maxProduct = item;

Your basic problem is 2 parts. Break them down and solving it becomes easier.

1) Find all contiguous subsets.

Since your source sequence can have negative values, you are not all that equipped to make any value judgments until you're found each subset, as a negative can later be "cancelled" by another. So let the first phase be to only find the subsets.

An example of how you might do this is the following code

// will contain all contiguous subsets 
var sequences = new List<Tuple<bool, List<int>>>();

// build subsets 
foreach (int item in source)
{
    var deadCopies = new List<Tuple<bool, List<int>>>();

    foreach (var record in sequences.Where(r => r.Item1 && !r.Item2.Contains(0)))
    {
        // make a copy that is "dead"
        var deadCopy = new Tuple<bool, List<int>>(false, record.Item2.ToList());
        deadCopies.Add(deadCopy);

        record.Item2.Add(item);
    }

    sequences.Add(new Tuple<bool, List<int>>(true, new List<int> { item }));
    sequences.AddRange(deadCopies);
}

In the above code, I'm building all my contiguous subsets, while taking the liberty of not adding anything to a given subset that already has a 0 value. You can omit that particular behavior if you wish.

2) Calculate each subset's product and compare that to a max value.

Once you have found all of your qualifying subsets, the next part is easy.

// find subset with highest product 
int maxProduct = int.MinValue;
IEnumerable<int> maxSequence = Enumerable.Empty<int>();

foreach (var record in sequences)
{
    int product = record.Item2.Aggregate((a, b) => a * b);
    if (product > maxProduct)
    {
        maxProduct = product;
        maxSequence = record.Item2;
    }
}

Add whatever logic you wish to restrict the length of the original source or the subset candidates or product values. For example, if you wish to enforce minimum length requirements on either, or if a subset product of 0 is allowed if a non-zero product is available.

Also, I make no claims as to the performance of the code, it is merely to illustrate breaking the problem down into its parts.

I think you should have 2 products at the same time - they will differ in signs. About case, when all values are zero - you can check at the end if maxProduct is still Int32.MinValue (if Int32.MinValue is really not possible) My variant:

int maxProduct = Int32.MinValue;
int? productWithPositiveStart = null;
int? productWithNegativeStart = null;

for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == 0)
        {
            productWithPositiveStart = null;
            productWithNegativeStart = null;
        } 
        else 
        {
            if (arr[i] > 0 && productWithPositiveStart == null) 
            {
                 productWithPositiveStart = arr[i];            
            }
            else if (productWithPositiveStart != null)
            {
                 productWithPositiveStart *= arr[i];
                 maxProduct = Math.max(maxProduct, productWithPositiveStart);
            }
            if (arr[i] < 0 && productWithNegativeStart == null)
            {
                 productWithNegativeStart = arr[i];
            }
            else if (productWithNegativeStart != null) 
            {
                 productWithNegativeStart *= arr[i];
                 maxProduct = Math.max(maxProduct, productWithNegativeStart);
            }
            maxProduct = Math.max(arr[i], maxProduct);
        }            
    }
 if (maxProduct == Int32.MinValue) 
 {
     maxProduct = 0;
 }

At a high level, your current algorithm splits the array upon a 0 and returns the largest contiguous product of these sub-arrays. Any further iterations will be on the process of finding the largest contiguous product of a sub-array where no elements are 0.

To take into account negative numbers, we obviously first need to test if the product of one of these sub-arrays is negative, and take some special action if it is.

The negative result comes from an odd number of negative values, so we need to remove one of these negative values to make the result positive again. To do this we remove all elements up the the first negative number, or the last negative number and all elements after that, whichever results in the highest product.

To take into account an array of all 0's, simply use 0 as your starting maxProduct. If the array is a single negative value, you're special case handling of a single element will mean that is returned. After that, there will always be a positive sub-sequence product, or else the whole array is 0 and it should return 0 anyway.

it can be done in O(N). it is based on the simple idea: calculate the minimum (minCurrent) and maximum (maxCurrent) till i. This can be easily changed to fit for the condition like: {0,0,-2,0} or {-2,-3, -8} or {0,0}

a[] = {6, -3, 2, 0, 3, -2, -4, -2, 4, 5}

steps of the algorithm given below for the above array a :

private static int getMaxProduct(int[] a) {
    if (a.length == 0) {
        throw new IllegalArgumentException();
    }
    int minCurrent = 1, maxCurrent = 1, max = Integer.MIN_VALUE;
    for (int current : a) {
        if (current > 0) {
            maxCurrent = maxCurrent * current;
            minCurrent = Math.min(minCurrent * current, 1);
        } else if (current == 0) {
            maxCurrent = 1;
            minCurrent = 1;
        } else {
            int x = maxCurrent;
            maxCurrent = Math.max(minCurrent * current, 1);
            minCurrent = x * current;
        }
        if (max < maxCurrent) {
            max = maxCurrent;
        }
    }
    //System.out.println(minCurrent);
    return max;
}