Задача о поиске лучшей сделки

Это еще одна классическая задача программирования о поиске некой лучшей пары чисел в массиве. Задача формулируется следующим образом.

Есть массив стоимости актива по дням, необходимо найти оптимальные точки покупки и продажи актива (входа и выхода из сделки). Обычно требуется найти максимальную величину прибыли в рамках периода, за который предоставлены данные.

Рассмотрим произвольные данные биржевой динамики актива. Мне кажется, и без вычислений очевидно, где здесь точки входа и выхода. Это будут M1 и X2.

Brute force

Если решать эту задачу «грубой силой», нам нужно перебрать все элементы массива слева направо (i), и для каждого из них вычислять разницу с оставшимися элементами справа (j). Максимальная дельта и будет искомой величиной.

Ясно, что уже даже для массива в 10000 элементов, такие вычисления потребует времени, так мы перебираем элементы вложенными циклами. Число вычислений в цикле составит порядка N * N / 2.

Местные экстремумы

Совершенно ясно также, что для каждой точки массива, нас интересуют только самая минимальная величина актива слева от точки и максимальная величина справа от точки. И мы можем вычислить эти величины за один проход цикла.

Еще один проход цикла позволит найти максимум разницы между минимумами и максимумами в каждой точке. Т.е. число итераций циклов составит порядка 2 * N.

Как видите, о затратах 2N можно говорить чисто формально, на деле это 3N, так как внутри первого цикла мы обращаемся к разным элементам массива. Хотя расчеты производятся существенно быстрее, но мы заплатили высокую цену в виде создания двух дополнительных массивов.

Поиск максимума

На самом деле мы делаем очень много лишних вещей, так как выполнить задачу можно с затратами порядка N и не создавая лишних массивов.

Двигаясь слева направо, нас интересует только самая минимальная точка слева. В то время как мы можем сравнивать её с каждым следующим значением и, таким образом, найти лучший результат за весь период всего за один проход цикла.

Мало букафф? Читайте есчо !

Игра в камни

Май 27, 2023 г.

Серия задач StoneGame на leetcode - образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого. Но это не наш случай, т.к. по условию ...

Читать

87. Scramble string - задача о перетасованных строках

Март 30, 2023 г.

Решаем задачу с литкода о перетасовке строки. Даны две строки, нужно определить является ли вторая строка результатом перетасовки букв в первой. Правила ...

Читать

Задача о поиске всех подходящих под-сум

Июль 1, 2023 г.

№560 leetcode Subarray Sum Equals K. Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k. В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если ...

Читать

Задача следующей комбинации (next permutation)

Март 13, 2023 г.

Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи. Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов. ...

Читать
 

Комментарии к «Задача о поиске лучшей сделки»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: