SPOJ : Weighted Sum

Question

You are given N integers, A[1] to A[N]. You have to assign weights to these integers such that their weighted sum is maximized. The weights should satisfy the following conditions :

1. Each weight should be an positive integer.
2. W[1] = 1
3. W[i] should be in the range [2, W[i-1] + 1] for i > 1

Weighted sum is defined as S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]

eg :

n=4 , array[]={ 1 2 3 -4 } , answer = 6 when we assign { 1 2 3 2 } respective weights .

So, as far as my understanding and research , no Greed solution is possible for it . I worked out many testcases on pen n paper , but couldn't get a greedy strategy .

Any ideas/hints/approaches people .

Answer 1

Let dp[i][j] equal the maximum weighted sum we can make from A[1..i] by assigning weight j to A[i]. Clearly dp[i][j] = j*A[i] + max(dp[i - 1][(j - 1)..N]). There are O(N^2) states and our recurrence takes O(N) for each state so the overall time complexity will be O(N^3). To reduce it to O(N^2) we can notice that there is significant overlap in our recurrence.

If dp[i][j] = j * A[i] + max(dp[i - 1][(j - 1)..N]), then

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])

Which means the recurrence takes only O(1) to compute, giving you O(N^2) time overall.

Answer 2

Here's a little insight that might enable you or someone else to come up with a really fast solution. Note that for an optimal solution, you can safely assume that at each step either you increase the weight by +1 from the previous weight, or you decrease the weight all the way down to the minimum of 2. To see this, suppose you have an optimal solution that violates the property. Then you have some weight > 2 at some position i-1 and the next weight is also > 2 at position i but not an increase. Now consider the maximal length weakly increasing sub-sequence of weights in the optimal solution starting at position i (weakly increasing means that at each step in the sub-sequence, the weight does not decrease). By assumption, the optimal solution with this sub-sequence is no worse than the same solution except with the sub-sequence having 1 subtracted from all its weights. But this means that increasing all the weights in the sub-sequence by 1 will also not make the optimal solution any worse. Thus for an optimal solution, at each step you can safely assume that either you increase the weight by 1 or you set the weight to the minimum of 2.

Answer 3

Fairly standard dynamic-programming methods can be used to solve this problem in O(N³) time. Let V(k,u) denote the best value that can be gotten using elements k...N when Wₖ₋₁ has the value u. Observe that V(k,u) is the maximum value of g·Aₖ+V(k-1,g) as g ranges from 2 to u+1, and that V(N,u) is (u+1)·A_N if A_N is positive, else 2·A_N.

Note that u is at most k in any V(k,u) calculation, so there are N*(N-1)/2 possible values of (k,u), so the method as outlined uses O(N²) space and O(N³) time.