给定阵列A,形成阵列M,使得乘积之和(a1*m1 + ... + an*mn)最大

Question

我最近接受了采访,在那里我被问到以下算法问题.我无法找到O(n)解决方案,也无法找到谷歌的问题.

给定整数的数组A [a_0 ... a_(n-1)](+ ve和-ve).形成一个数组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开始并且只要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. 继续重复直到到达数组末尾。

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