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 ≤ 10⁵ and |a_i| ≤ 10¹². Naively, it can be computed in O(n²). 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(n²).

Any hints would be appreciated.