algorithm - SPOJ : Weighted Sum -

you given n integers, a[1] a[n]. have assign weights these integers such weighted sum maximized. weights should satisfy following conditions :

1. each weight should positive integer.
2. w[1] = 1
3. w[i] should in range [2, w[i-1] + 1] > 1

weighted sum defined s = a[1] * w[1] + a[2] * w[2] + ... + a[n] * w[n]

eg :

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

so, far understanding , research , no greed solution possible . worked out many testcases on pen n paper , couldn't greedy strategy .

any ideas/hints/approaches people .

let dp[i][j] equal maximum weighted sum can make a[1..i] assigning weight j a[i]. dp[i][j] = j*a[i] + max(dp[i - 1][(j - 1)..n]). there o(n^2) states , our recurrence takes o(n) each state overall time complexity o(n^3). reduce o(n^2) can notice there 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 recurrence takes o(1) compute, giving o(n^2) time overall.