arrays - 求解最大积子数组的正确方法

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 算法 的变体。我只是想弄清楚我的方法是否完全错误。

Answer 1

你的算法失败了，因为当数组中的负值 a 使负值 maxEndingHere 为正值时，a 再也不会被视为新子序列的可能第一个值。

示例数组中的第 3 个^rd 元素 (-2) 就是这种情况(我忽略了它前面的 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);