找到在整数数组最大的产品

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

您的基本问题是2部分。打破它们并解决它变得更容易。

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的子集产品。

另外，我对代码的性能没有任何要求，它仅仅是为了说明将问题分解成各个部分。

Answer 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 3

在高层次上，你的当前算法将数组拆分为0并返回这些子数组的最大连续乘积。任何进一步的迭代将在寻找子阵列中没有元素为0的最大连续产品的过程中。

要考虑负数，我们显然首先需要测试这些子元素之一的乘积 - 数组是消极的，如果是的话，采取一些特殊的行动。

负面结果来自奇数个负值，因此我们需要移除其中一个负值以使结果再次成为正值。为此，我们删除第一个负数上的所有元素，或者最后一个负数，以及之后的所有元素，取其中最高的产品。

要考虑所有0的数组，只需使用0作为您的起始maxProduct。如果数组是单个负值，则对特定情况的单个元素处理意味着返回。之后，总会有一个正的子序列产品，否则整个数组为0，无论如何它应该返回0。

Answer 4

我基于我的答案假设，如果你有超过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; 

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