在整数数组中查找具有最大乘积的连续序列

Question

我已经提出了下面的代码但是并不满足所有情况,例如:

1. 包含全0的数组

2. 具有负值的数组(它有点棘手,因为它是关于将产品看作是两个负的整数给出正值)

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

如何合并上述案例/更正代码.请建议.

Answer 1

你的基本问题有两部分。分解它们并解决它变得更容易。

1）找到所有连续的子集。

由于源序列可能具有负值，因此在找到每个子集之前，您无法做出任何值判断，因为负值稍后可能会被另一个子集“取消”。因此，让第一阶段只找到子集。

以下代码是您如何执行此操作的示例

// 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。

另外，我不对代码的性能做出任何声明，它只是为了说明将问题分解为几个部分。