Re: The problem of "maximum-subarray" on the example of the dollar

After reading the recent article "The problem of" maximum-subarray "on the example of the dollar" 3 times, I wanted to spit. The article proposes to find a period of dates for which it was possible to earn the most on the difference in the dollar / ruble exchange rate over the past 5 years. The author offers his “beautiful” solution to this problem, which he found himself (divide and conquer is called, yeah), and which works for O (n lg n) ...

Comrades, it’s a shame and a shame to publish the “Algorithms” blog that is obviously not the optimal solution to a trivial task. The maximum sum of the subarray elements in the array is searched for O (n)! If only Wikipedia was honored for this task .

The normal solution is under the cut.
')
In fact, there is even no need to “prepare” anything. In the article, everything is turned upside down. The quotes are the preliminary data for solving the "maximum-subarray" problem. The problem solved by the author is not limited to the problem "maximum-subarray". On the contrary, the solution to the “maximum-subarray” problem comes down to what the author tried to do. All that needs to be found is such indices i <= j for some array A, so that A [j] -A [i] is maximum (or minimum).

The task of finding two dates, the difference in the values ​​of the courses for which is maximum, is reduced to finding such a local maximum A [j], so that the difference between it and the previous minimum A [i] absolute on the segment (0, j) is maximum . This is a typical example of dynamic programming , the implementation is also clearer and looks much shorter than the solution given by the author:

def find(A): currentMin = 1e308 currentMinIndex = None maxDiff = -1e308 bestResult = None for i, v in enumerate(A): if v < currentMin: currentMin, currentMinIndex = v, i if v - currentMin > maxDiff: maxDiff, bestResult = v - currentMin, (currentMinIndex, i) return bestResult, maxDiff 

Here currenctMin, currentMinIndex is the current minimum value of the quote and its index on the interval (0, i). At the i-th step, the current best result is compared with the difference between the current course value and the preceding minimum course (currentMin). If the current difference is greater - it is recorded as the best, and so on until the end. The language of mathematics:

 maxDiff (0) = -infinity
 maxDiff (i) = max (maxDiff (i-1), A [i] - min (A [0: i])), 
           where min (A [0: i]) is the minimum value from 0 to i.

References:
Previous topic
Maximum subarray problem
Dynamic programming

Ps. I would not publish the answer in a separate article, if the previous topic did not go to the main. Forgive me.