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.