Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 31
Правильно ли я понимаю, что мне нужно знать будущее, чтобы разбогатеть таким образом?
Да, асболютно верно, ну или хотя бы курс с утраи немного анализа с имеющимися данными.
Не обязательно. Можно вычислить с какой периодичностью повторяются события в мире и на основе полученных данных рассчитать следующий скачек (%
Я работал вот в этой, она пишет софт, которые рассчитывает цену на электроэнергию на будущее, заказчики, соответственно, муниципалитеты, крупные предприятия, энергетические компании и т.д. (контора — гавно если че). Кроме того, что они собирают информацию из почти 1000 источников в реальном времени (от цен на биржах, до количества выпавшего снега в горах — больше снега, больше воды для гидростанций, меньше цена), но там и математика такая, что мне с матобразованием университета там делать нечего.
Так что для заработать денег, как мне кажется, одной статьи будет недостаточно.
Так что для заработать денег, как мне кажется, одной статьи будет недостаточно.
Для этого достаточно заполучить подобный журнальчик на будущий сезон:
Если я правильно понял условие, то есть решение проще и за O(n).
Условие: найти в массиве два элемента a<b таких, что v[a]-v[b] — максимально.
Решение: давайте соптимизируем лобовое решение. Заметим, что при фиксированном a наилучшим выбором b будет такое, в котором v[b] минимально. Тогда давайте перебирать a от больших к меньшим и на каждом шаге помнить минимум справа. При уменьшении a минимум либо остается на месте, либо сдвигается в позицию, где мы только что стояли. Получаем линейное решение.
При этом задача «найти подотрезок с максимальной суммой» также сводится к исходной — предподсчитаем суммы на всех префиксах массива. Тогда сумма на подотрезке будет как раз равна разности двух значений.
Условие: найти в массиве два элемента a<b таких, что v[a]-v[b] — максимально.
Решение: давайте соптимизируем лобовое решение. Заметим, что при фиксированном a наилучшим выбором b будет такое, в котором v[b] минимально. Тогда давайте перебирать a от больших к меньшим и на каждом шаге помнить минимум справа. При уменьшении a минимум либо остается на месте, либо сдвигается в позицию, где мы только что стояли. Получаем линейное решение.
При этом задача «найти подотрезок с максимальной суммой» также сводится к исходной — предподсчитаем суммы на всех префиксах массива. Тогда сумма на подотрезке будет как раз равна разности двух значений.
Для примера найти 2 элемента тоже верно, но моё решение покрывает несколько больший пласт задач, т.к. мы ищем максимальную сумму элементов подмассива
максимальная сумма элементов подмассива в массиве
Или вы не правильно сформулировали или я чего-то не понимаю,
Но для неотрицательных элементов это просто весь массив.
Вашу же задачу сформулировал yeputons.
В любом случае есть решение за O(N).
Фух, по меньшей мере один нормальный человек есть. Мне плеваться захотелось, когда я увидел статью в разделе «Алгоритмы» с очевидно не оптимальным решением тривиальной задачи.
Так я и не спорю, что есть O(N) решение, zvulon чуть ниже привёл его. К сожалению, мало кто постарался найти лучшее, чем в статье.
В той книге эта задача рассматривалась как пример метода «Разделяй и влавствуй», так что это решение имеет право на жизнь.
А перечитал, вы все же ищите в массиве разностей, тогда вот решение за O(N).
import random
rnd = random.Random()
INF = 1000000
def get_max_subarray(arr):
best_sum = -INF
cur_sum = 0
left, right = 0,0
while right < len(arr):
new_el = arr[right]
cur_sum = cur_sum + new_el
if cur_sum > best_sum: # update best sum.
best_sum = cur_sum
(best_left, best_right) = (left , right)
if new_el < 0: # worst than best. restart
cur_sum = 0
left = right + 1
right += 1 #next
return (best_left, best_right, best_sum)
#example
x = [ rnd.randint(-100000, 100000) for _ in range(0,200) ]
#print x
y = get_max_subarray(x)
print y
Поправка
должно быть
if new_el < 0: # worst than best. restartдолжно быть
if new_el < 0 and cur_sum < best_sum: # worst than best. restartСпасибо за то, что нашли более эффективное решение!
В вики ещё более лаконично:
В вики ещё более лаконично:
def max_subarray(A):
max_so_far = max_ending_here = 0
for x in A:
max_ending_here = max(0, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
Не будет работать, может быть ситуация, когда подмассив с отрицательными элементами даст большую сумму, чем меньший без них, например [10, -1, 100].
Алгоритм бесполезен даже для аналитических задач, особенно в валютных торгах. Трейдера не интересует единственная лучшая транзакция, гораздо интереснее с вероятностью > 0.6 угадывать начало и конец тренда.
Даже достаточно более-менее качественно прогнозировать вход в позицию, а далее ММ вытягивать из сделки максимум прибыли/минимум убытка.
Что касается статьи — это больше похоже на отчет по прочтению книги, пример. Для реального применения, торговли строго по дневкам и строго разово — такая аналитика малополезна на мой взгляд, даже для выявления циклов.
Что касается статьи — это больше похоже на отчет по прочтению книги, пример. Для реального применения, торговли строго по дневкам и строго разово — такая аналитика малополезна на мой взгляд, даже для выявления циклов.
Так как вы программируете на Python, то советую прочитать увлекательную книгу Python Algorithms: Mastering Basic Algorithms in the Python Language, в ней эта же самая проблема рассматривается в составе divide-and-conquer алгоритмов, и итоговый код, насколько я помню, красивый и компактный.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Проблема «maximum-subarray» на примере курса доллара