The editorial and other published solutions for this problem have at least O(n log n) time complexity. Here is a O(n) solution.

tl;dr for those who solved this problem with the Convex Hull Trick is that we can keep lines in a queue rather than a tree/sorted list, because we only add lines of increasing/decreasing slope. This solution doesn't require conceptualizing the geometry though .

Explanation with examples

We have 2 cases: moving an item forwards or backwards. Since they are mirrors of each other, I'll only talk about the forwards case.

We iterate from 2->n and for each index we want to answer "which previously seen item is the best choice to move here?". We're going to build a queue where the first item of the queue is always the answer to this question. Why is this possible? Let's look at some examples:

[6,2,3,9,0,0,0] Input
[-,6,6,6,6,9,9] Best choice

To start, we put an item representing the 6 into our queue. As we pass through 2 and 3 we calculate the value for moving the 6 there, but we don't have to consider adding 2 or 3 to the queue. Intuitively, we want the small items to the left and the large items to the right. When we move from left to right and a new item is smaller than the largest item we've previously seen, it's always better to move the large item many steps rather than the small item fewer steps.

We reach 9 and it's larger than 6, so we consider adding it to the queue. We want to know at what point it becomes better to move the 9 rather than the 6. Well, if we moved the 6 onto the 9 we would gain 6*3 and lose (9+2+3) = 4. We can consider this value as the "head start" that 6 has over 9. Then each additional step that we move the 6, we gain +6-t[i]. If we moved 9 instead of 6, each step would yield +9-t[i]. So each step further 9 "catches up" 6 by 3 points. This means that we can trivially calculate the index where 9 becomes a better choice.

After 9 we have 2 items in the queue:

FIRST = [0,1] (where 0 is the index for 6 and 1 is the index where 6 becomes the best choice to move)
LAST = [3,5] (where 3 is the index for 9 and 5 is the index where 9 becomes the best choice to move)

We could also have more than 2 items in the queue. Imagine the following input:

[5,0,0,0,0,0,6,0,0,7,0,0,0,0...]

Intuitively, 5 will be the best choice to move for a long time. At some point 6 takes over, then 7 takes over. We're going to have 3 items in the queue. It's not obvious why the last item is always added to the end of the queue, or at least it's not obvious to me. Let's think about the following input:

[5,0,6,1000,0,0]

When we reach the 1000 it becomes the best item to move, so we want to put it to the front of the queue, right? Well, not exactly. 5 and 6 become obsolete so we want to remove them from the queue, then we add 1000 to the end of the (now empty) queue. This is still pretty obvious, but can we say for sure there's never a case where we would want to add something to the middle of the queue? Remember that every item we add is larger than the largest previously seen item. Remember also that the larger item always "catches up" in score as you step more to the right. This means that once a larger item becomes best choice, it's impossible for a smaller item to become best choice later on. Thus, we always add items to the end of the queue, after possibly removing obsolete items. Sometimes we also need to remove obsolete items from the front of the queue. As for time complexity, whenever we read more than 3 items from the queue, we are removing items. Each item can only be added once (and thus can only be removed once). This gives us O(n) time complexity.

The geometric version of this explanation would be that our queue represents the Convex Hull and we can add to the end of the queue because we only add lines of increasing slope. When we want to get the "current line" of the Convex Hull we can — rather than binary/ternary searching — just read the first item of the queue, because as we step to the right we erase obsolete lines off the convex.

Here is my commented java implementation.

Here is a better C++ implementation by ffao (edited into this post)

I struggled with my Convex Hull Trick implementation for a long time so it was pretty satisfying to find an alternate solution with better time complexity. Thanks to zscefn, pllk, Laakeri and OliKoJo for helping me debug & helping me understand the geometry behind this.