正確的方法來解決產品的最大子陣

Question

我試圖解決這個問題：

由於包含正反兩方面的整數，找到最大的產品子陣列的產品陣列。 假設：總有一個積極的產品可能，即沒有這種形式的數組：{0，-20,0,0}或{-20}。

例：

6 -3 -10 0 2 
ANS = 180 

2 3 4 5 -1 0 
ANS = 120 

8 -2 -2 0 8 0 -6 -8 -6 -1 
ANS = 288 

我的解決方案：

public static void main(String arg[]) { 
    ArrayList<Integer> arr = new ArrayList<Integer>(); 
    // FAILS FOR THIS TEST CASE 
    // 9 0 8 -1 -2 -2 6 
    arr.add(9); 
    arr.add(0); 
    arr.add(8); 
    arr.add(-1); 
    arr.add(-2); 
    arr.add(-2); 
    arr.add(6); 

    int maxEndingHere = 1; 
    int minEndingHere = 1; 
    int max_so_far = 1; 

    for (int k = 0; k < arr.size(); k++) { 
     maxEndingHere = maxEndingHere * arr.get(k); 
     if (maxEndingHere < 0) { 
     minEndingHere = minEndingHere * maxEndingHere; 
     if (minEndingHere > 0) { 
      maxEndingHere = minEndingHere; 
      minEndingHere = 1; 
     } else { 
      maxEndingHere = 1; 
     } 
     } 

     if (maxEndingHere == 0) { 
     maxEndingHere = 1; 
     minEndingHere = 1; 
     } 

     if (max_so_far < maxEndingHere) { 
     max_so_far = maxEndingHere; 
     } 
    } 
    System.out.println(max_so_far); 
    } 

對於其中數組的值是9 0 8 -1 -2 -2 6的情況下我的解決辦法未能。正確的答案是24，但我得到了16.有人能幫我弄清楚我的方法是否錯誤？

我已閱讀其他解決方案的問題，其中大部分是kadane的算法的變化。我只是想弄清楚我的方法是否完全錯誤。因爲當一個負值陣列中的作出了否定的maxEndingHere積極

Answer 1

你的算法失敗，那一個永遠不會再被視爲一個新的子序列的可能第一個值。

這與在該樣本陣列3 ^RD元件（-2）的情況下（I忽略9 0它之前）：

8 -1 -2 -2 6 

即-2，該算法具有處理之後設置maxEndingHere到16，這是迄今爲止最好的結果。但隨後算法繼續以下-2，並開始新產品（因爲minEndingHere是1並且變成-2）。中間-2不會被重複用於可能發揮作用的可能的新序列。這樣一來，算法只發現-2 * 6，而不是-2 * -2 * 6

我建議下面的算法，這似乎更直觀，也以線性時間運行：

看子序列由0值分隔。然後，如果這些值的乘積是正數，那麼它就是候選人。如果是負值，請查看以下兩個操作中的哪一個產生最高產品：

• 從左側刪除值，直到幷包括第一個負值，並相應地調整產品;
• 從右側刪除值，直到包括最後的負值，並相應地調整產品;

這給出了一個積極的產品，並使其成爲候選人。

終於跟蹤哪個候選人是最大的產品。

下面是簡單的JavaScript實現的算法：

function maxProduct(a) { 
 
    var i, j, product, productLeft, productRight, best; 
 
    
 
    best = 0; 
 
    product = 1; 
 
    productLeft = 0; 
 
    i = 0; 
 
    
 
    for (j = 0; j <= a.length; j++) { // go one index too far 
 
     if (j == a.length || a[j] == 0) { // end of non-zero sequence 
 
      if (j > i) { // there is at least one value in this sub sequence 
 
       if (product < 0) { // need to remove a negative factor 
 
        product /= productLeft < productRight // NB: both are negative 
 
         ? productRight : productLeft; 
 
       } 
 
       if (product > best) { 
 
        best = product; 
 
       } 
 
      } 
 
      // reset for next sub sequence 
 
      product = 1; 
 
      productLeft = 0; 
 
      i = j + 1; 
 
     } else { 
 
      product *= a[j]; 
 
      if (a[j] < 0) { 
 
       // Keep track of product until first negative value 
 
       if (productLeft == 0) { 
 
        productLeft = product; 
 
       } 
 
       productRight = 1; 
 
      } 
 
      // Keep track of product from last negative value onwards 
 
      productRight *= a[j]; 
 
     } 
 
    } 
 
    return best; 
 
} 
 

 
// Sample data 
 
a = [9, 0, 8, -1, -2, -2, 6]; 
 

 
// Get max product 
 
result = maxProduct(a); 
 

 
// Output array and result 
 
console.log(a.join(',')); 
 
console.log(result);

Answer 2

爲什麼你不說出你的變量的含義，並通過您的代碼步時看到/他們是否發展爲你期望他們？

我想你的假設是，在每一步之後，變量maxEH（minEH）應該代表在數組中相應位置結束的最大正數（最小負數）乘積，或者如果沒有正數（負數） 。因此，假設將這些值制定如下：

• 9 - >（9,1）一樣代碼]
• 0 - >（1,1）相同]
• （1，-8）[相同]
• -2 - >（16，-2）[你的代碼說：（16,1） - >（8,1）[相同]
• -1 - > ]
• -2 - >（4，-32）[...前FALSO ...]
• 6 - >（24，-192）

所以，如果我對你的意圖是正確的，那麼 a） 這個想法是健全的 ，b）你的代碼有缺陷，c）你的代碼看起來太複雜。我建議打開arr [k]的符號以使事情變得更簡單。

添加到a）：我相信你的方法是不可能正確實現的。如果您有更長的負數序列（至少，如果我正確地猜出了您的預期不變量），維護minEH/maxEH將始終失敗。以-2 -3 -4 -5 -6 -7。你的maxEh/minEH序列應該是（1/-2），（6,1），（12，-24），（120，-60）。你的代碼甚至不會計算這些值。顯然，它打破了第一個負數序列。