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

«Алгоритмы: построение и анализ», «Искусственный интеллект: современный подход» и другие книги по свободной цене

Programming *
Недавно ребята из books.ru в очередной раз пополнили раздел электронных книг, предлагаемых по свободной цене. Акция продажи новых электронных изданий будет идти до 1 июня (судя по опыту прошлых акций свободная цена на некоторые книги сохранится и в будущем).

Но в любом случае, я бы не стал писать этот пост, если бы не увидел, что коллекция пополнилась настоящими бриллиантами. «Алгоритмы: построение и анализ (CLRS), 2-е издание» (Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн) (читал эту книгу в печатном варианте и могу сказать, что перевод просто отменный). Искусственный интеллект: современный подход (AIMA-2), 2-е издание (Стюарт Рассел, Питер Норвиг).

С момента первого анонса о свободной цене в раздел добавились книги Нильсена, Брукса, Фаулера, Прата, Степанова, Спольски, Физерса, Александреску и др. Под катом находятся около 40 новых книг, которые больше всего заслуживают внимания (спрятаны под спойлер).
Читать дальше →
Total votes 56: ↑53 and ↓3 +50
Views 62K
Comments 34