Решение: лучшее время для покупки и продажи акций с платой за транзакцию

LeetCode Solutions (161 серия деталей)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

Проблема LeetCode #714 (средний): лучшее время для покупки и продажи акций с платой за транзакцию

Описание:

( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++

Вам дают массив цены где Цены [i] цена данной акции на i День, и целое число плата представляя плату за транзакцию.

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

Примечание : Вы не можете участвовать в нескольких транзакциях одновременно (то есть вы должны продать акцию, прежде чем покупать снова).

Примеры:

Ограничения:

• 1 <Цены. Длина * 10^4
• 0 <цен [i], плата <5 * 10^4

Идея:

( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++

Этот проплем является введением в Государственная машина логика. Чтобы решить его, мы можем рассмотреть два возможных отдельных состояния бытия: отсутствие запасов и готовые к покупке ( Покупка ) и владение акциями и готовые к продаже ( Продажа ).

Нам просто нужно итерацию по ценам ( P ) и отслеживать наилучшее возможное значение для этих двух состояний для каждого дня. Трудность заключается в том, что треки двух штатов регулярно пересекаются.

Например, если мы рассмотрим состояние готового купить акции после этой итерации ( Покупка ), с ним можно достичь из -за того, что он готов купить сегодня и ничего не делать, Или Это может быть достигнуто, будучи готовым к продаже сегодня и продажи (с дополнительной платой [ F ]). Нам просто нужно выбрать все, что дает лучшее значение.

То же самое относится и к Продажа государство. Новый Продажа Состояние – лучший результат между предыдущим Продажа Государство без действий и предыдущего Покупка Государство с покупкой акций сегодня.

Мы должны вручную установить наши начальные значения для Покупка а также Продажа учитывать первый день и итерацию оттуда.

Поскольку плата администрируется только один раз за пару покупок/продажи, мы можем технически учитывать его с обеих сторон, так как мы всегда захотим вернуть Покупка Государство, не имея непогашенных акций, чтобы продать.

Вопрос: Должны ли мы беспокоиться об обновлении покупки перед использованием его во втором уравнении? Математически, это только хороший день, чтобы купить или продавать; Это не может быть и то и другое.

Рассмотрим возможные ситуации: в первом уравнении, если старое Покупка больше, чем Продажа + P [i] – f , тогда новый Покупка будет таким же, как старый Покупка , поэтому не будет никаких изменений для второго уравнения.

Но что, если Покупка изменения? Давайте приведем пример:

  if:  buy = 10, P[i] = 4, F = 0
then:  newBuy = max(10, sell + 4 - 0)
       newSell = max(sell, newBuy - 4)

  if:  sell <= 6                          // For values of sell less than 7
then:  newBuy = max(10, <=10)             // the old buy will still be largest
       newBuy = buy                       // so there's no problem

  if:  sell > 6                           // If sell is greater than 6
then:  newBuy = max(10, >6 + 4)           // then buy will change
       newBuy = sell + 4                  // so we might have a problem

  if:  newBuy = sell + 4                  // But here we see that sell cannot
then:  newSell = max(sell, sell + 4 - 4)  // possibly change when buy does

Любое положительное значение для F В приведенном выше примере только снижает значение newbuy , что только сделало бы так, чтобы newbuy – p [i] даже не мог связать Продать но всегда будет ниже.

Реализация:

Код для всех четырех языков почти идентичен.

Код JavaScript:

( Прыгните к : Описание задачи Идея решения

var maxProfit = function(P, F) {
    let len = P.length, buying = 0, selling = -P[0]
    for (let i = 1; i < len; i++) {
        buying = Math.max(buying, selling + P[i] - F)
        selling = Math.max(selling, buying - P[i])
    }
    return buying
};

Код Python:

( Прыгните к : Описание задачи Идея решения

class Solution:
    def maxProfit(self, P: List[int], F: int) -> int:
        buying, selling = 0, -P[0]
        for i in range(1, len(P)):
            buying = max(buying, selling + P[i] - F)
            selling = max(selling, buying - P[i])
        return buying

Код Java:

( Прыгните к : Описание задачи Идея решения

class Solution {
    public int maxProfit(int[] P, int F) {
        int len = P.length, buying = 0, selling = -P[0];
        for (int i = 1; i < len; i++) {
            buying = Math.max(buying, selling + P[i] - F);
            selling = Math.max(selling, buying - P[i]);
        }
        return buying;
    }
}

C ++ Код:

( Прыгните к : Описание задачи Идея решения

class Solution {
public:
    int maxProfit(vector& P, int F) {
        int len = P.size(), buying = 0, selling = -P[0];
        for (int i = 1; i < len; i++) {
            buying = max(buying, selling + P[i] - F);
            selling = max(selling, buying - P[i]);
        }
        return buying;
    }
};

LeetCode Solutions (161 серия деталей)

Оригинал: “https://dev.to/seanpgallivan/solution-best-time-to-buy-and-sell-stock-with-transaction-fee-5dlp”