Question: Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference between the elements of the array and the elements of progression. Thus one needs to minimize the sum of absolute differences. It is a restriction that the values must be integers:
$1, 5, 10, 14, 19 \to 0, 5, 10, 15, 20$

It is easy to solve it with the help of linear programming without restriction to integers. But even the simplex method and other similar algorithms are not sufficient because they can handle cases when $N \leq 10^5$. In this case, the integers can be rather large (i believe up to $10^7$). Is there any algorithm for solving it in $O(N\log^k M)$ or even $O(N)$, where $M$ is the maximum integer value of an array?

Answer: 
The continuous case is that of finding the [Least absolute deviation](https://en.wikipedia.org/wiki/Least_absolute_deviations). Not easily tractable, but you may find libraries that are more efficient that the LP formulation.

[Iteratively reweighted least-squares](https://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares) is not too hard to implement yourself. If you are not looking for the optimum, a simple least-square could do.
Why not compute the mean value of the consecutive differences in the array and use it as a progression value? The mean will naturally be a real value, however you could always round it or ceil it. This gives you 2 progression values. You could try both and use the one with less distance. This way the algorithm might run in $O(N)$ time. Correct me if I misunderstood.