给你N 个整数，从 A[1] 到 A[N]。您必须为这些整数分配权重，以便它们的weighted sum is maximized. 重量应满足以下条件：
加权和定义为 S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]
例如：
n=4 , array[]={ 1 2 3 -4 } , answer = 6 when we assign { 1 2 3 2 } respective weights .
因此，据我的理解和研究，没有贪婪的解决方案是可能的。我在 pen n 纸上设计了许多测试用例，但无法得到一个贪婪的策略。
任何想法/提示/接近人。
让dp[i][j]等于我们可以A[1..i]通过将权重分配给j来得出的最大加权和A[i]。显然dp[i][j] = j*A[i] + max(dp[i - 1][(j - 1)..N])。有O(N^2)状态，每个状态我们的递归都需要O(N)，所以整体时间复杂度将是O(N^3)。为了减少它，O(N^2)我们可以注意到我们的递归中有很大的重叠。
如果dp[i][j] = j * A[i] + max(dp[i - 1][(j - 1)..N])，那么
dp[i][j - 1] = (j - 1)*A[i] + max(dp[i - 1][(j - 2)..N]) = (j - 1)*A[i] + max(dp[i - 1][j - 2], dp[i - 1][(j - 1)..N]) = (j - 1)*A[i] + max(dp[i - 1][j - 2], dp[i][j] - j*A[i])
这意味着重复只需要 O(1) 来计算，给你 O(N^2) 的时间。
可以使用相当标准的动态规划方法在 O(N³) 时间内解决这个问题。令 V(k,u) 表示当 Wₖ₋₁ 具有值 u 时使用元素 k...N 可以获得的最佳值。观察到V(k,u)是g·Aₖ+V(k-1,g)的最大值，因为g的范围是2到u+1，V(N,u)是(u+1)·如果 A N为正，则为 A N ，否则为 2· A N。
请注意，在任何 V(k,u) 计算中 u 最多为 k，因此 (k,u) 有 N*(N-1)/2 个可能值，因此概述的方法使用 O(N²) 空间和O(N³) 时间。
这里有一些见解，可能使您或其他人能够想出一个非常快速的解决方案。请注意，对于最佳解决方案，您可以放心地假设在每一步中，您将权重从前一个权重增加 +1，或者将权重一直降低到最小值 2。要看到这一点，假设您有违反性质的最优解。然后你在某个位置有一些体重> 2，i-1下一个体重也在位置> 2，i但没有增加。现在考虑从位置开始的最优解中权重的最大长度弱增加子序列i（弱增加意味着在子序列的每一步，权重都不会减少）。通过假设，这个子序列的最优解并不比相同的解差，除了子序列的所有权重都减去 1。但这意味着将子序列中的所有权重增加 1 也不会使最优解变得更糟。因此，对于最佳解决方案，您可以在每一步安全地假设您将权重增加 1 或将权重设置为最小值 2。