找到在整數數組最大的產品

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