给定数组A，形成数组M使得乘积之和(a1*m1+...+an*mn)最大化。

Question

我最近接受了一次采访，在采访中被问到了以下算法问题。我没有能力找到O(n)的解决方案，也无法通过谷歌找到这个问题。

给定一个整数数组 A[a_0 ... a_(n-1)]（包含正数和负数），生成一个数组 M[m_0 ... m_(n-1)]，其中m_0 = 2，且m_i ∈ [2,...,m_(i-1)+1]，使得乘积总和最大化，即要最大化a_0*m_0+a_1*m_1+...+a_(n-1)*m_(n-1)

示例：

input  {1,2,3,-50,4}
output {2,3,4,2,3}

input  {1,-1,8,12}
output {2,3,4,5}

我的O(n^2)解决方案是从m_0 = 2开始逐个增加1，只要a_i为正数。如果a_i < 0，则我们必须考虑从2到m_i-1 + 1的所有m_i，并查看哪个产生最大的乘积和。

请提出一个线性时间算法。

- khallas

Answer 1

假设您有以下数组：

1, 1, 2, -50, -3, -4, 6, 7, 8.

在每个条目处，我们可以继续增加进度，也可以将值重置为较低的值。
这里只有两个好的选择。要么我们选择当前条目的最大可能值，要么选择最小可能值(2)。(证明在结尾) 现在很清楚，我们输出的前三个条目应该是2、3和4(因为到目前为止所有的数字都是正数，没有理由将它们重置为2(一个较低的值))。

当遇到负数时，计算总和：
-(50 + 3 + 4) = -57。

接下来计算连续的正数之和：
(6 + 7 + 8) = 21。

由于57大于21，所以重置第四个条目为2是有意义的。

再次计算负数条目的总和：
-(3 + 4) = -7。

现在7小于21，因此不需要进一步重置，因为如果正数值很高，就可以获得最大乘积。

因此，输出数组应该是：

2, 3, 4, 2, 3, 4, 5, 6, 7

为了使这个算法在线性时间内工作，您可以预先计算将在计算中所需的总和数组。

证明：

当遇到负数时，我们可以将输出值重置为低值（比如j）或继续增加（比如i）。

假设有k个负值和m个连续的正值。

如果我们将值重置为j，则这k个负值和m个正值的乘积值应为：

- ( (j-2+2)*a1 + (j-2+3)*a2 + ... + (j-2+k+1)*ak ) + ( (j-2+k+2)*b1 + (j-2+k+3)*b2 + ... + (j-2+k+m+1)*am )

如果我们不将值重置为2，则这些k个负数和m个正数的产品值将相等：

- ( (i+2)*a1 + (i+3)*a2 + (i+4)*a3 ... + (i+k+1)*ak ) + ( (i+k+2)*b1 + (i+k+3)*b2 + ... + (i+k+m+1)*am )

因此，上述两个表达式之间的差异在于：

(i-j+2)* ( sum of positive values - sum of negative values )

这个数字可以是正数也可以是负数。因此，我们将倾向于使j尽可能高（M [i-1] +1）或尽可能低（2）。

在O（N）时间内预先计算数组的总和

编辑：正如Evgeny Kluev所指出的那样

1. 向后遍历数组。
2. 如果遇到负元素，则忽略它。
3. 如果遇到正数，则将后缀总和设置为该值。
4. 继续将元素的值添加到总和中，直到它仍然为正数。
5. 一旦总和变成小于0，记录这个点。这是分离重置为2并继续增加的决策点。
6. 再次忽略所有负值，直到达到正值。
7. 重复以上步骤，直到到达数组末尾。

注意：在计算后缀总和时，如果遇到零值，则可能存在多个解决方案。

- Abhishek Bansal

---

我认为这是一个不错的方法。但是为什么只重置为2？2是最小可能值，但它可以一直增加到M[i-1]+1。而且我认为它仍然是O(n^2)。此外，当数值为负数时递增是没有意义的，因此-(502 + 33 + 44)应该是-(502 + 32 + 42)。请注意，M[i]允许的最小和最大值为[2，M[i-1]+1]。 - khallas

@khallas 这个算法是O(N)的，因为你可以预先计算出和值并将其存储在数组中。至于正确性，老实说我不确定。 - Abhishek Bansal

@khallas 如果是负数，增量也可能有意义。例如，如果数组是{-1，-1，-1，50，50}，那么我们也会为负数增加，因为这样我们可以获得更高的输出值，以便后续的正数（50）能够更大。 - Abhishek Bansal

你说得对，只有两个好的选择。获取适当算法所需的唯一缺失细节是我们需要向后处理数组：跳过尾随的负（和零）元素，然后在后缀和仍为正时计算后缀和，并重复这两个步骤，直到遇到数组的开头。顺便说一句，我们还可以跟踪值为零的后缀和，以回答相关问题：这个问题有多少不同的解决方案。 - Evgeny Kluev

@EvgenyKluev 没有看到我们可以通过反向迭代计算决策点。感谢您提供的两个指针！（这个和值为零的后缀和） - Abhishek Bansal

Answer 2

感谢Abhishek Bansal和Evgeny Kluevfor提供的伪代码。 这是Java代码。

 public static void problem(int[] a, int[] m) {
        int[] sum = new int[a.length];
        if(a[a.length-1] > 0)
          sum[a.length-1] = a[a.length-1];
        for(int i=a.length-2; i >=0; i--) {
          if(sum[i+1] == 0 && a[i] <= 0) continue;
          if(sum[i+1] + a[i] > 0) sum[i] = sum[i+1] + a[i];
        }
        //System.out.println(Arrays.toString(sum));
        m[0] = 2;
        for(int i=1; i < a.length; i++) {
          if(sum[i] > 0) {
            m[i] = m[i-1]+1;
          } else {
            m[i] = 2;
          }
        }
      }

- khallas