DP Optimisation Problem

Revision en2, by likecs, 2017-06-17 16:06:38

How can we optimise dynamic programming of the form:

Base case : dp[i] = a[i] * i

dp[i] = max(dp[i], dp[j] + (a[i] - a[j]) * (i - j)), for 1 ≤ j < i

It is given that n ≤ 105 and |ai| ≤ 1012. Naively, it can be computed in O(n2). But I can't further improve my solution.

I tried the following :

(a[i] - a[j]) * (i - j) = a[i] * i + a[j] * j - a[i] * j - a[j] * i

Thus, we can store another array, dp2[i] = dp[i] + a[i] * i. Then the recurrence becomes :

Base case : dp[i] = 0

dp[i] = max(dp[i], dp2[j] - a[i] * j - a[j] * i)

Finally : dp[i] = dp[i] + a[i] * i and dp2[i] = dp[i] + a[i] * i

But, it is still O(n2).

Any hints would be appreciated.

Tags dynamic programming, optimisation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English likecs 2017-06-17 16:06:38 3
en1 English likecs 2017-06-17 15:27:16 727 Initial revision (published)