Pull to refresh

Comments 31

Правильно ли я понимаю, что мне нужно знать будущее, чтобы разбогатеть таким образом?
Да, асболютно верно, ну или хотя бы курс с утраи немного анализа с имеющимися данными.
Не обязательно. Можно вычислить с какой периодичностью повторяются события в мире и на основе полученных данных рассчитать следующий скачек (%
Главное чтобы случайно не оказалось, что все события в мире повторяются с периодом в 100 000 000 000 лет — от большого взрыва до большого коллапса.
Я работал вот в этой, она пишет софт, которые рассчитывает цену на электроэнергию на будущее, заказчики, соответственно, муниципалитеты, крупные предприятия, энергетические компании и т.д. (контора — гавно если че). Кроме того, что они собирают информацию из почти 1000 источников в реальном времени (от цен на биржах, до количества выпавшего снега в горах — больше снега, больше воды для гидростанций, меньше цена), но там и математика такая, что мне с матобразованием университета там делать нечего.

Так что для заработать денег, как мне кажется, одной статьи будет недостаточно.
А почему говно? А то меня в одну похожую контору позвали(экономическая физика), может скажете, чего опасаться.
Нет, в той конторе к предметной области это отношения не имеет, это руководство такое.
Для этого достаточно заполучить подобный журнальчик на будущий сезон:

Sports Almanac
Мне привезёте версию с нейтринным рекламным экранчиком внутри? Хочу попробовать на его Windows X поставить, авось заведётся.
эх, классный был фильм. Посмотрел раз 5)
Особенно ржачно сейчас смотреть на тамошний 2015 год.
А я тут недавно посмотрел «Гостья из будущего», правда 1 серию, на большее меня не хватило. Там вот супер техника — особенно интерфейс машины времени меня порадовал
всего 5 раз? Слабак!
UFO just landed and posted this here
Если я правильно понял условие, то есть решение проще и за O(n).
Условие: найти в массиве два элемента 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 алгоритмов, и итоговый код, насколько я помню, красивый и компактный.
Only those users with full accounts are able to leave comments. Log in, please.