c# - 在整数数组中找到具有最大乘积的连续序列

我想出了下面的代码，但是不能满足所有情况，例如:

包含所有0的

的数组

具有负值的数组(因为要寻找乘积，因为两个负整数给出正值，所以有点棘手)

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

如何合并以上情况/更正代码。请提出建议。

最佳答案

您的基本问题是2个部分。分解它们，解决它变得容易。

1)查找所有连续的子集。

由于您的源序列可以具有负值，因此在找到每个子集之前，您都不具备进行任何值(value)判断的能力，因为负数以后可以被另一个“取消”。因此，让第一阶段为仅找到子集。

下面的代码是一个如何执行此操作的示例

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

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

关于c# - 在整数数组中找到具有最大乘积的连续序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5973970/