Предположим, нам дан массив из n целых чисел, представляющих курсы акций за один день. Мы хотим найти пару (buyDay, sellDay) с buyDay ≤ sellDay , чтобы, если бы мы купили акции в buyDay и продали их в sellDay , мы бы максимизировали нашу прибыль.
Очевидно, что существует решение алгоритма за O (n 2 ), если опробовать все возможные пары (buyDay, sellDay) и извлечь из них все самое лучшее. Однако есть ли лучший алгоритм, возможно, тот, который работает за O (n) время?
arrays
algorithm
big-o
time-complexity
Аджит Ганга
источник
источник
Ответы:
Я люблю эту проблему. Это классический вопрос на собеседовании, и в зависимости от того, как вы к нему относитесь, в конечном итоге вы найдете все более и более удачные решения. Конечно, можно сделать это быстрее, чем за O (n 2 ), и я перечислил здесь три различных способа, которыми вы можете подумать о проблеме. Надеюсь, это ответит на ваш вопрос!
Во-первых, решение «разделяй и властвуй». Посмотрим, сможем ли мы решить эту проблему, разделив входные данные пополам, решив проблему в каждом подмассиве, а затем объединив их вместе. Оказывается, мы действительно можем это сделать, и можем делать это эффективно! Интуиция такова. Если у нас один день, лучший вариант - купить в этот день, а затем продать его обратно в тот же день без прибыли. В противном случае разделите массив на две половины. Если мы подумаем о том, какой может быть оптимальный ответ, он должен быть в одном из трех мест:
Мы можем получить значения для (1) и (2), рекурсивно вызывая наш алгоритм на первой и второй половинах. Для варианта (3) способом получения максимальной прибыли будет покупка в самой низкой точке в первой половине и продажа в самой высокой точке во второй половине. Мы можем найти минимальное и максимальное значения в двух половинах, просто выполнив простое линейное сканирование по входу и найдя два значения. Это дает нам алгоритм со следующей повторяемостью:
Используя основную теорему для решения рекурсии, мы обнаруживаем, что это выполняется за время O (n lg n) и будет использовать пространство O (lg n) для рекурсивных вызовов. Мы только что обыграли наивное решение O (n 2 )!
Но ждать! Мы можем добиться большего, чем это. Обратите внимание, что единственная причина, по которой у нас есть член O (n) в нашем повторении, заключается в том, что нам пришлось сканировать весь ввод, пытаясь найти минимальное и максимальное значения в каждой половине. Поскольку мы уже рекурсивно исследуем каждую половину, возможно, мы сможем добиться большего, если рекурсия также вернет минимальные и максимальные значения, хранящиеся в каждой половине! Другими словами, наша рекурсия возвращает три вещи:
Эти последние два значения могут быть вычислены рекурсивно, используя простую рекурсию, которую мы можем запустить одновременно с рекурсией для вычисления (1):
Если мы воспользуемся этим подходом, наше рекуррентное отношение теперь будет
Использование основной теоремы дает нам время выполнения O (n) с пространством O (lg n), что даже лучше, чем наше исходное решение!
Но подождите минутку - мы можем сделать даже лучше, чем это! Давайте подумаем о решении этой проблемы с помощью динамического программирования. Идея будет заключаться в следующем. Предположим, что мы знали ответ на проблему, посмотрев на первые k элементов. Можем ли мы использовать наши знания о (k + 1) -м элементе в сочетании с нашим начальным решением, чтобы решить проблему для первых (k + 1) элементов? Если это так, мы могли бы получить отличный алгоритм, решив проблему для первого элемента, затем для первых двух, затем для первых трех и т. Д., Пока мы не вычислим его для первых n элементов.
Давайте подумаем, как это сделать. Если у нас есть только один элемент, мы уже знаем, что это должна быть лучшая пара покупки / продажи. Теперь предположим, что мы знаем лучший ответ для первых k элементов, и посмотрим на (k + 1) -й элемент. Тогда единственный способ, которым это значение может создать решение лучше, чем то, что мы имели для первых k элементов, - это если разница между наименьшим из первых k элементов и этим новым элементом больше, чем самая большая разница, которую мы вычислили до сих пор. Итак, предположим, что, просматривая элементы, мы отслеживаем два значения - минимальное значение, которое мы видели до сих пор, и максимальную прибыль, которую мы могли бы получить только с первыми k элементами. Изначально минимальное значение, которое мы видели до сих пор, является первым элементом, а максимальная прибыль равна нулю. Когда мы видим новый элемент, Сначала мы обновляем нашу оптимальную прибыль, вычисляя, сколько мы могли бы заработать, купив по самой низкой цене, наблюдаемой до сих пор, и продав по текущей цене. Если это лучше, чем оптимальное значение, которое мы вычислили до сих пор, то мы обновляем оптимальное решение, чтобы оно было новой прибылью. Затем мы обновляем минимальный элемент, который мы видели до сих пор, чтобы он был минимальным из текущего наименьшего элемента и нового элемента.
Поскольку на каждом шаге мы выполняем только O (1) работу и посещаем каждый из n элементов ровно один раз, это занимает O (n) времени! Более того, он использует только вспомогательную память O (1). Это так хорошо, как мы уже сделали!
В качестве примера на ваших входных данных вот как может работать этот алгоритм. Числа между каждым из значений массива соответствуют значениям, удерживаемым алгоритмом в этой точке. На самом деле вы бы не стали хранить все это (это заняло бы O (n) памяти!), Но было бы полезно увидеть, как алгоритм развивается:
Ответ: (5, 10)
Ответ: (4, 12)
Ответ: (1, 5)
Можем ли мы сделать лучше сейчас? К сожалению, не в асимптотическом смысле. Если мы используем время меньше O (n), мы не сможем просмотреть все числа на больших входных данных и, следовательно, не сможем гарантировать, что не пропустим оптимальный ответ (мы могли бы просто «спрятать» его в элементах, которые мы не смотрел). Кроме того, мы не можем использовать пространство меньше O (1). Могут быть некоторые оптимизации постоянных факторов, скрытых в нотации большого O, но в противном случае мы не можем ожидать найти какие-либо радикально лучшие варианты.
В целом это означает, что у нас есть следующие алгоритмы:
Надеюсь это поможет!
РЕДАКТИРОВАТЬ : Если вам интересно, я закодировал версию этих четырех алгоритмов для Python, чтобы вы могли поиграть с ними и оценить их относительную производительность. Вот код:
источник
Это задача подпоследовательности максимальной суммы с небольшим косвенным обращением. Задача о максимальной сумме подпоследовательности задается списком целых чисел, которые могут быть положительными или отрицательными, найти наибольшую сумму непрерывного подмножества этого списка.
Вы можете тривиально преобразовать эту проблему в проблему, зафиксировав прибыль или убыток между днями подряд. Таким образом, вы можете преобразовать список цен на акции, например,
[5, 6, 7, 4, 2]
в список прибылей / убытков, например[1, 1, -3, -2]
. Тогда довольно просто решить проблему суммы подпоследовательностей: найдите подпоследовательность с наибольшей суммой элементов в массивеисточник
Я не совсем уверен, почему это считается вопросом динамического программирования. Я видел этот вопрос в учебниках и руководствах по алгоритмам, использующим время выполнения O (n log n) и O (log n) для пространства (например, Elements of Programming Interviews). Это кажется гораздо более простой проблемой, чем люди думают.
Это работает путем отслеживания максимальной прибыли, минимальной цены покупки и, следовательно, оптимальной цены покупки / продажи. Проходя через каждый элемент в массиве, он проверяет, меньше ли данный элемент минимальной цены покупки. Если это так, индекс минимальной закупочной цены (
min
) обновляется до индекса этого элемента. Кроме того, для каждого элементаbecomeABillionaire
алгоритм проверяет,arr[i] - arr[min]
превышает ли (разница между текущим элементом и минимальной ценой покупки) текущую прибыль. Если это так, прибыль обновляется до этой разницы, и устанавливается значение покупки,arr[min]
а значение продажи -arr[i]
.Работает за один проход.
Соавтор: https://stackoverflow.com/users/599402/ephraim
источник
Задача идентична максимальной подпоследовательности.
Я решил ее с помощью динамического программирования. Следите за текущим и предыдущим (прибыль, дата покупки и дата продажи). Если текущее значение выше предыдущего, замените предыдущее на текущее.
источник
вот мое решение Java:
источник
Я придумал простое решение - код более понятен. Это один из тех вопросов динамического программирования.
Код не заботится о проверке ошибок и крайних случаях. Это просто образец, чтобы дать представление об основной логике решения проблемы.
источник
Вот мое решение. изменяет алгоритм максимальной подпоследовательности. Решает проблему за O (n). Я думаю, что это невозможно сделать быстрее.
источник
Это интересная проблема, потому что она кажется сложной, но тщательное обдумывание дает элегантное и урезанное решение.
Как уже отмечалось, это может быть решено перебором за время O (N ^ 2). Для каждой записи в массиве (или списке) перебирайте все предыдущие записи, чтобы получить минимальное или максимальное значение в зависимости от того, заключается ли проблема в поиске наибольшего прироста или убытка.
Вот как думать о решении в O (N): каждая запись представляет новый возможный максимум (или минимум). Затем все, что нам нужно сделать, это сохранить предыдущий минимум (или максимум) и сравнить разницу с текущим и предыдущим минимумом (или максимумом). Очень просто.
Вот код на Java как тест JUnit:
В случае расчета наибольшего убытка мы отслеживаем максимум в списке (цену покупки) до текущей записи. Затем мы вычисляем разницу между максимальной и текущей записью. Если max - current> maxLoss, то мы сохраняем эту разницу в качестве нового maxLoss. Поскольку индекс max гарантированно будет меньше, чем индекс текущего, мы гарантируем, что дата «покупки» меньше даты «продажи».
В случае расчета наибольшего усиления все происходит наоборот. Мы отслеживаем мин в списке до текущей записи. Мы вычисляем разницу между min и текущей записью (меняя порядок вычитания). Если current - min> maxGain, то мы сохраняем эту разницу в качестве нового maxGain. Опять же, индекс «покупка» (мин.) Стоит перед индексом «текущей» («продажа»).
Нам нужно только отслеживать maxGain (или maxLoss) и индекс min или max, но не оба сразу, и нам не нужно сравнивать индексы, чтобы убедиться, что «покупка» меньше, чем «продажа», поскольку мы получить это естественно.
источник
Максимальная прибыль от одной продажи, решение O (n)
Вот проект, который выполняет тестирование временной сложности на подходах o (N) vs o (n ^ 2) на случайном наборе данных на 100k int. O (n ^ 2) занимает 2 секунды, а O (n) - 0,01 секунды
https://github.com/gulakov/complexity.js
Это более медленный, o (n ^ 2) подход, который проходит через оставшиеся дни для каждого дня, двойной цикл.
источник
Ответ, получивший наибольшее количество голосов, не допускает случаев, когда максимальная прибыль отрицательна, и его следует изменить, чтобы учесть такие случаи. Это можно сделать, ограничив диапазон цикла до (len (a) - 1) и изменив способ определения прибыли, сдвинув индекс на единицу.
Сравните эту версию функции с предыдущей для массива:
источник
источник
Возможность определить максимальную прибыль может заключаться в отслеживании левого минимума и правого максимума элементов в массиве по каждому индексу в массиве. Когда вы затем перебираете цены на акции, для каждого дня вы будете знать самую низкую цену до этого дня, а также максимальную цену после (включительно) этого дня.
Например, давайте определим
min_arr
иmax_arr
с заданным массивомarr
. Индексi
inmin_arr
будет минимальным элементомarr
для всех индексов<= i
(слева и включая i). Индексi
inmax_arr
будет максимальным элементомarr
для всех индексов>= i
(справа и включая i). Затем вы можете найти максимальную разницу между соответствующими элементами вmax_arr
и `min_arr ':Это должно выполняться за O (n) время, но я считаю, что он занимает много места.
источник
Это максимальная разница между двумя элементами в массиве, и это мое решение:
O (N) временная сложность O (1) пространственная сложность
источник
После того, как я провалил этот экзамен по программированию на должность инженера по решениям FB, мне пришлось решать его в спокойной прохладной атмосфере, так что вот мои 2 цента:
источник
Единственный ответ, действительно отвечающий на вопрос, - это ответ @akash_magoon (и такой простой способ!), Но он не возвращает точный объект, указанный в вопросе. Я немного реорганизовал, и мой ответ в PHP возвращает именно то, что спрашивают:
источник
Аккуратное решение:
источник
Эта программа на python3 может возвращать цену покупки и цену продажи, которые максимизируют прибыль, вычисленную с временной сложностью O (n) и пространственной сложностью O (1) .
источник
Вот мое решение
источник
Для всех ответов, отслеживающих минимальные и максимальные элементы, это решение фактически является решением O (n ^ 2). Это потому, что в конце необходимо проверить, произошел ли максимум после минимума или нет. Если это не так, требуются дальнейшие итерации, пока это условие не будет выполнено, и это оставляет наихудший случай O (n ^ 2). А если вы хотите пропустить лишние итерации, потребуется гораздо больше места. В любом случае, нет-нет по сравнению с решением динамического программирования
источник