Максимизация прибыли при заданных котировках акций
Мне задали этот вопрос во время интервью для стартапа, и я снова увидел это в недавнем конкурсе на
** Вопрос:
Вам даны цены на акции за набор дней. Каждый день вы можете покупать одну единицу акций, продавать любое количество единиц, которые вы уже купили, или ничего не делать. Какую максимальную прибыль вы можете получить, оптимально спланировав свою торговую стратегию? **
Примеры (ввод, т.е. количество дней, может варьироваться)
5 3 2 => profit = 0 // поскольку цена уменьшается с каждым день, максимальная прибыль, которую мы можем получить = 0
1 2 100 => profit = 197
1 3 1 2 => profit = 3 // мы покупаем по 1, продаем по 3, затем покупаем по 1 и продаем при 2 ..общая прибыль = 3
Мое решение:
а) Найдите день, когда цена акции была максимальной. Продолжайте покупать 1 шт. На складе до этого дня.
б) Если этот день последний, то выйти:
иначе:
Продайте все акции в этот день и разделите массив после этого дня и выполните рекурсию по оставшимся элементам
c) объединить прибыль
, например, 1 4 1 2 3
а) наивысшая цена акций на второй день ..поэтому мы покупаем акции в день 1 и продаем их в день 2 (прибыль = 3), затем мы выполняем рекурсию в оставшиеся дни: 1 2 3
б) Максимальная цена равна 3 (в день 5), поэтому мы продолжаем покупать акции в день 3 и 4 день и продать в день 5 (прибыль = (3 * 2 - 3 = 3)
c) Общая прибыль = 3 + 3 = 6
Сложность для этого оказывается O (n ^ 2 ). это решение прошло 10 из 11 случаев, но превысило ограничение по времени в последнем тестовом примере (т.е. самый большой ввод)
Итак, мой вопрос: может ли кто-нибудь придумать более эффективное решение этой проблемы? Есть ли динамическое решение программное решение?
P.S: я впервые задаю здесь вопрос. дайте мне знать, если мне нужно улучшить / добавить что-то в этот вопрос