Вам дан массив prices, где prices[i] — цена данной акции на ith день.

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

  • После того, как вы продали свои акции, вы не можете купить акции на следующий день (т. е. один день восстановления).

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

Пример 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Пример 2:

Input: prices = [1]
Output: 0

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

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

Решения:

Питон

class Solution(object):
    def maxProfit(self, prices):
        if not prices:
            return 0

        n = len(prices)
        buy = [0] * n
        sell = [0] * n
        cooldown = [0] * n

        buy[0] = -prices[0]
        sell[0] = 0
        cooldown[0] = 0

        for i in range(1, len(prices)):
            buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i])
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])
            cooldown[i] = max(cooldown[i - 1], sell[i - 1])

        return max(sell)

C#

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0)
        {
            return 0;
        }

        int n = prices.Length;
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] cooldown = new int[n];

        buy[0] = -prices[0];
        sell[0] = 0;
        cooldown[0] = 0;

        for (int i = 1; i < prices.Length; i++)
        {
            buy[i] = Math.Max(buy[i - 1], cooldown[i - 1] - prices[i]);
            sell[i] = Math.Max(sell[i - 1], buy[i - 1] + prices[i]);
            cooldown[i] = Math.Max(cooldown[i - 1], sell[i - 1]);
        }

        return Math.Max(sell.Max(), cooldown.Max());
    }
}

Ява

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] cooldown = new int[n];

        buy[0] = -prices[0];
        sell[0] = 0;
        cooldown[0] = 0;

        for (int i = 1; i < prices.length; i++) {
            buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
            cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
        }

        return Math.max(sell[n - 1], cooldown[n - 1]);
    }
}

JavaScript

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length === 0) {
        return 0;
    }

    const n = prices.length;
    const buy = new Array(n).fill(0);
    const sell = new Array(n).fill(0);
    const cooldown = new Array(n).fill(0);

    buy[0] = -prices[0];
    sell[0] = 0;
    cooldown[0] = 0;

    for (let i = 1; i < prices.length; i++) {
        buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i]);
        sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
    }

    return Math.max(sell[n - 1], cooldown[n - 1]);
};

Типографический текст

function maxProfit(prices: number[]): number {
    if (prices.length === 0) {
        return 0;
    }

    const n = prices.length;
    const buy = new Array(n).fill(0);
    const sell = new Array(n).fill(0);
    const cooldown = new Array(n).fill(0);

    buy[0] = -prices[0];
    sell[0] = 0;
    cooldown[0] = 0;

    for (let i = 1; i < prices.length; i++) {
        buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i]);
        sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
    }

    return Math.max(sell[n - 1], cooldown[n - 1]);
};

PHP

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        if (count($prices) == 0) {
            return 0;
        }

        $n = count($prices);
        $buy = array_fill(0, $n, 0);
        $sell = array_fill(0, $n, 0);
        $cooldown = array_fill(0, $n, 0);

        $buy[0] = -$prices[0];
        $sell[0] = 0;
        $cooldown[0] = 0;

        for ($i = 1; $i < count($prices); $i++) {
            $buy[$i] = max($buy[$i - 1], $cooldown[$i - 1] - $prices[$i]);
            $sell[$i] = max($sell[$i - 1], $buy[$i - 1] + $prices[$i]);
            $cooldown[$i] = max($cooldown[$i - 1], $sell[$i - 1]);
        }

        return max($sell[$n - 1], $cooldown[$n - 1]);
    }
}

Надеюсь, это поможет! Дайте знать, если у вас появятся вопросы. Не забудьте подписаться, похлопать и оставить комментарий