Pull to refresh

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

Algorithms *

В чём суть


В статье предлагается найти промежуток дат, за который можно было заработать больше всего на разнице в курсе доллара к рублю за последние 5 лет.
image
На русском языке наименование проблемы будет звучать примерно как максимальная сумма элементов подмассива в массиве. В статье приведен алгоритм вычислений, а так же результат его работы.
Читать дальше →
Total votes 70: ↑40 and ↓30 +10
Views 6.7K
Comments 31

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

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

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

Нормальное решение под катом.
Читать дальше →
Total votes 190: ↑182 and ↓8 +174
Views 2.9K
Comments 30