В чём суть
В статье предлагается найти промежуток дат, за который можно было заработать больше всего на разнице в курсе доллара к рублю за последние 5 лет.
На русском языке наименование проблемы будет звучать примерно как максимальная сумма элементов подмассива в массиве. В статье приведен алгоритм вычислений, а так же результат его работы.
Как я к этому пришёл
Недавно начал читать отличную книгу CLRS (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third Edition.). Как не трудно догадаться, в книге изложены фундаментальные знания computer science.
Один из разделов книги как раз приводит реализацию алгоритма для решения этой проблемы. Для закрепления знаний и удовлетворения собственного интереса, я решил применить его на данных о курсе доллара к рублю за последние 5 лет.
Суть проблемы
Как видно из графика за последние 5 лет курс доллара менялся очень сильно. И было бы разумно предположить, что наверняка самой выгодной сделкой было бы купить в абсолютный минимум и продать в последующий локальный максимум (который порой не так легко обнаружить «на глаз»).
Давайте проверим это утверждение.
Решение
Самым простым решением было бы «пойти в лоб» и перебором найти суммы всех комбинаций субмассивов и сравнить их на поиск максимального, однако это решение займёт по времени O(n^2) не очень нас устраивает, так как есть уверенность, что можно сделать это оптимальнее.
Решением будем рекурсивно разбивать входной массив на 2 подмассива через середину и искать максимальную сумму в каждой и частей, а так же на их пересечении. Данный процесс будет требовать у нас O(n lg n), что вполне эффективно.
Давайте распишем пример:
Данные мы получим из www.oanda.com/currency/historical-rates в .csv файле в формате
"2011-10-02","32.1914",,,,
"2011-10-01","32.0809",,,,
"2011-09-30","31.9086",,,,
"2011-09-29","31.7294",,,,
"2011-09-28","32.0421",,,,
"2011-09-27","32.2233",,,,
"2011-09-26","32.0980",,,,
"2011-09-25","32.0673",,,,
...
Далее нам надо считать данные и подготовить их для обработки:
courses = [] reader = csv.reader(open('data.csv', 'rb'), delimiter=',', quotechar='"') prev = 0 for row in reader: #получить текущий элемент cur = float(row[1]) #в самом начале разницы в курсе не должно быть if prev == 0: prev = cur #сохраним разницу в списке value = [row[0], prev - cur, row[1]] prev = cur courses.insert(0, value)
Данные в файле в обратном порядке относительно времени, поэтому вставляем их инверсно. Во время обработки данных мы ищем разницу в ежедневном курсе previous — current. Нашей задачей как раз и будет поиск максимальной суммы этих разностей.
def find_max_subarray(a, low, high): #выход из рекурсии if high == low: return low, high, a[low][1] else: #разбиваем массив на 2 части mid = (low + high) / 2 #находим максимум в левой части left_low, left_high, left_sum = find_max_subarray(a, low, mid) #находим максимум в правой части right_low, right_high, right_sum = find_max_subarray(a, mid + 1, high) #находим кросс-максимум cross_low, cross_high, cross_sum = find_crossing(a, low, mid, high) if (left_sum >= right_sum) & (left_sum >= cross_sum): return left_low, left_high, left_sum elif (right_sum >= left_sum) & (right_sum >= cross_sum): return right_low, right_high, right_sum else: return cross_low, cross_high, cross_sum
И функция поиска кросс-максимума (проходящего через mid — середину деления).
def find_crossing(a, low, mid, high): max_left = 0 max_right = 0 left_sum = -1e308 sum = 0 #уходим влево от центра for i in range(mid, low, -1): sum = sum + a[i][1] if sum > left_sum: left_sum = sum max_left = i max_right = 0 right_sum = -1e308 sum = 0 #уходим вправо от центра for j in range(mid + 1, high): sum = sum + a[j][1] if sum > right_sum: right_sum = sum max_right = j return max_left, max_right, left_sum + right_sum
Ну и выведем результат, который нас интересует
min, max, sum = find_max_subarray(courses, 0, len(courses)-1) print courses[min] print courses[max] print sum
В результате я получил
['2008-07-16', 0.07420000000000115, '23.1269']
['2009-02-05', 0.12059999999999604, '36.1257']
13.1194
И немного поигрался, сдвинув нижнюю дату на 2011 год
['2011-05-05', 0.006199999999999761, '27.2657']
['2011-09-26', 0.12530000000000285, '32.0980']
4.9576
Весь код можно найти на gist.github.com/1257729
Спасибо за внимание!
