Pull to refresh

Re: Проблема «maximum-subarray» на примере курса доллара

Reading time 2 min
Views 3.3K
После прочтения недавней статьи «Проблема «maximum-subarray» на примере курса доллара» 3 раза, мне захотелось плеваться. В статье предлагается найти промежуток дат, за который можно было заработать больше всего на разнице в курсе доллара к рублю за последние 5 лет. Автор предлагает свое «красивое» решение этой задачи, которое он нашел сам (разделяй и властвуй называется, ага), и которое работает за O(n lg n)…

Товарищи, это стыд и срам в блог «Алгоритмы» публиковать очевидно не оптимальное решение тривиальной задачи. Максимальная сумма элементов подмассива в массиве ищется за O(n)! Хоть бы википедию почитали по этой задаче.

Нормальное решение под катом.

На самом деле там даже «предподготавливать» ничего не нужно. В статье все перевернуто вверх ногами. Котировки и есть предподготовленныe данныe для решения задачи «maximum-subarray». Задача, решаемая автором не сводится к задаче «maximum-subarray». Наоборот — решение проблемы «maximum-subarray» сводится к тому, что попытался сделать автор. Все что нужно найти, это такие индексы i <= j для некоторого массива A, чтобы A[j]-A[i] было максимальным (или минимальным).

Задача найти две даты, разница значения курсов для которых максимальна, сводится к тому, что бы найти такой локальный максимум A[j], чтобы разница между ним и предшествующим ему абсолютным на отрезке (0, j) минимумом A[i] была максимальна. Это типичный пример динамического программирования, реализация к тому же понятнее и выглядит куда короче, чем приведенное автором решение:

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


Здесь currenctMin, currentMinIndex — текущее минимальное значение котировки и его индекс на промежутке (0, i). На i-ом шаге текущий наилучший результат сравнивается с разницей между текущим значением курса и предшествующим ему минимальным курсом (currentMin). Если текущая разница больше — она записывается как лучшая, и так до конца. Языком математики:

maxDiff(0) = -infinity
maxDiff(i) = max(maxDiff(i-1), A[i] - min(A[0:i])), 
          где min(A[0:i]) - минимальное значение на промежутке от 0 до i.


Ссылки:
Предыдущий топик
Maximum subarray problem
Динамическое программирование

PS. Я бы не публиковал ответ отдельной статьей, если бы предыдущий топик не вышел на главную. Простите меня.
Tags:
Hubs:
+174
Comments 30
Comments Comments 30

Articles