正确的方法来解决产品的最大子阵

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）。你的代码甚至不会计算这些值。显然，它打破了第一个负数序列。