logo标签列表

在一个整数数组中找到连续的序列，使其乘积最大。

c#.netarraysalgorithm
5
我已经编写了下面的代码，但它并不能满足所有情况，例如：

  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;
}
如何将上述情况纳入/更正代码。请提供建议。
5个回答
2
我假设您的数组中有多于1个元素，您想要至少乘以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;
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 的子集产品。

此外，我不保证代码的性能，它只是为了说明将问题分解成其部分。

0

从高层次上来看，您当前的算法将数组在0处分割，并返回这些子数组中最大连续乘积。任何进一步的迭代都将是查找一个子数组的最大连续乘积，其中没有元素为0的过程。

为了考虑负数，我们显然首先需要测试这些子数组之一的乘积是否为负数，并在必要时采取一些特殊措施。

负结果来自奇数个负值，因此我们需要删除其中一个负值以使结果再次变为正数。为此，我们删除所有第一个负数或最后一个负数之前的元素以及之后的所有元素，以产生最高的乘积。

为了考虑全0数组，只需使用0作为您的起始maxProduct。如果数组是单个负值，则您对单个元素的特殊处理将意味着返回该值。之后，总会有一个正的子序列乘积，否则整个数组都是0，应该返回0。

0

这可以在O(N)的时间复杂度内完成。它基于一个简单的想法：计算到i为止的最小值（minCurrent）和最大值（maxCurrent）。这可以很容易地改变以适应条件，如：{0,0,-2,0}或{-2,-3,-8}或{0,0}

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

以下是上述数组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;
}
0

我认为你应该同时拥有两个产品 - 它们将在符号上有所不同。 关于所有值都为零的情况 - 你可以在最后检查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;
 }
感谢提供的解决方案，但是上面的代码对于下面带有负数值的数组无法正常工作。 {-1，-15，-30，0，-17，2}：它应该返回450作为最大乘积，但实际上返回了15。 - user751025
@bhakti，-1 * -15 * -30 是 -450。此外，这应该是对那个答案的评论。 - Anthony Pegram
非常抱歉，因为我是用智能手机发布的。我试图在Nikita的帖子下找到“添加评论”链接，但没有找到。在上面的负数数组中，代码应该只返回-15 * -30的乘积，因为这些是返回最大乘积的连续元素。 - user751025
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接