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

Question

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

Given an array A[a_0 ... a_(n-1)] of integers (+ve and -ve). Form an array M[m_0 ... m_(n-1)] where m_0 = 2 and m_i in [2,...,m_(i-1)+1] such that sum of products is maximum i.e. we have to maximize 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 开始，只要 a_i 为 +ve 就继续递增 1。如果 a_i < 0，我们必须考虑从 2 到 m_i-1 + 1 的所有 m_i，看看哪个产生最大的乘积。

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

Answer 1

假设您有以下数组:

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

在每个条目中，我们可以继续递增的进程或将值重置为较低的值。
这里只有两个好的选择。我们要么选择当前条目的最大可能值，要么选择最小可能值 (2)。 (最后证明)

现在很明显，我们输出中的前 3 个条目应该是 2、3 和 4(因为到目前为止所有数字都是正数，没有理由将它们重置为 2(低值)。

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

接下来计算连续 +ve 个连续数字的相似和。
(6 + 7 + 8) = 21。

由于 57 大于 21，因此将第 4 个条目重置为 2 是有意义的。

再次计算负项的总和:
-(3 + 4) = -7。

现在 7 小于 21，因此不进一步重置是有意义的，因为如果正值很高，则应获得最大乘积。

因此输出数组应为:

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

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

证明:

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

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

如果我们将值重置为 j，则这些 k -ve 值和 m +ve 值的乘积值应等于:

- ( (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 -ve 值和 m +ve 值的乘积值应等于:

- ( (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. 不断重复，直到到达数组末尾。

注意:在计算后缀和时，如果遇到零值，则可以有多个这样的解。