В чём суть
В статье предлагается найти промежуток дат, за который можно было заработать больше всего на разнице в курсе доллара к рублю за последние 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
Спасибо за внимание!
