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

Question

I came up with the code below, but this does not satisfy all cases, for example:

• Array of all 0

• An array that has negative values ​​(it's a bit complicated, because it's about finding a product as two negative integers gives a 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 include the above cases / fix the code. Please suggest.

Answer 1

Your main problem is 2 parts. Break them down and make the solution easier.

1) Find all adjacent subsets.

, , , - , , . , .

, ,

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

, , 0. , .

2) .

, , .

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

, . , 0 , .

, , .

Answer 2

, , 2 , .. {-1, 15}, -15, 15).

, , - .

n nC2, .. 2 , 1, 3 - 3, 4 - 6, .

, , , , , , .

.

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

, , , {-1, 15} 15, , , . for .

if (item > maxProduct)
    maxProduct = item;

Answer 3

, 2 - . , , , maxProduct - Int32.MinValue( Int32.MinValue ) :

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

Answer 4

0 . , 0.

, , , , , - , .

, , . , , .

0, 0 maxProduct. , , , . , 0, 0.

Answer 5

O(N). : (minCurrent) (maxCurrent) i. , : {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;
}