There are two key observations.

1. Obviously, higher k means smaller result.
2. For every i (1 < i < n) there is res(i + 1) - res(i) ≤ res(i) - res(i - 1).

The above implies that for every i (that 1 ≤ i ≤ n) there exists such real value X that res(i) + i·X ≤ res(j) + j·X for every . Also, for fixed i good X's are between res(i + 1) - res(i) and res(i) - res(i - 1), inclusive (except for trivial cases k = 1 and k = n).

So, when we have fixed X, we can calculate the minimum value of dividing sequence into intervals (we can use any number of them), where cost for an interval is the same as in the basic version of task plus X. Using the convex hull trick, we can do it in O(n). Then we check how many intervals we've used to do it. If we've used too many, we know that X should be greater (to force the algorithm to use smaller number of intervals). If we've used at most k intervals, we should make X lower. So now we see that we should use binary search to find good X!

After finding good X, we just calculate the optimum value for full sequence and subtract k·X. This gives us O(n·log) solution.