股票问题

发现大佬总结的非常好...

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3

tql...

第一题： Best Time to Buy and Sell Stock

只允许发生一次交易

先想到的是只有一次买入和一次卖出，对于买入的时间和卖出的时间进行讨论就可以得出O(n^2)的算法

考虑改进 是不是可以只讨论卖出的时间点，而买入的时间点是从开始到卖出时间点这段时间的最小值

定义变量res表示最大差价 变量premin表示之前的最小值 代码非常清晰

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        res = 0
        premin = float("inf")
        
        for n in prices:
            res = max(res, n - premin)
            premin = min(premin, n)
        return res

将六道题的代码给出 解释以后再补

class Solution(object):
    def maxProfit_one(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        cur0, cur1 = 0, -float("inf"),
        for p in prices:
            cur0 = max(cur0, cur1 + p)
            cur1 = max(cur1, -p) # 如何限制的交易次数 状态1不可以由状态0转变
        return cur0

    def maxProfit_any(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        cur0, cur1 = 0, -float("inf")
        for p in prices:
            pre0 = cur0
            cur0 = max(cur0, cur1 + p)
            cur1 = max(cur1, pre0 - p)
        return cur0

    def maxProfit_any_cool(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        pre0, cur0, cur1 = 0, 0, -float("inf") # -2 -1 -1 天
        for p in prices:
            temp = cur0  # -1
            cur0 = max(cur0, cur1 + p)
            cur1 = max(cur1, pre0 - p)
            pre0 = temp  # -1 变成 -2 窗口右移
        return cur0

    def maxProfit_any_fee(self, prices, fee):
        """
        :type prices: List[int]
        :rtype: int
        """
        cur0, cur1 = 0, -float("inf")
        for p in prices:
            pre0 = cur0
            cur0 = max(cur0, cur1 + p - fee)
            cur1 = max(cur1, pre0 - p)
        return cur0

    def mamProfit_2(self, prices):
        dp = [[0] * 2 for _ in range(3)]
        for i in range(3):
            dp[i][1] = -float("inf")
        for i in range(len(prices)):
            for k in [1, 0]:
                dp[k][0] = max(dp[k][0], dp[k][1] + prices[i])
                # dp[k][1] = max(dp[k][1], (dp[k - 1][0] if k - 1 >= 0 else 0) - prices[i])
                dp[k][1] = max(dp[k][1], dp[k - 1][0] - prices[i])
        return dp[1][0]

    def maxProfit_K(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k > len(prices) // 2:  # 因为内存超出限制 报错
            self.maxProfit_any(prices)

        dp = [[0] * 2 for _ in range(k + 1)]

        for i in range(k + 1):
            dp[i][1] = -float("inf")

        for i in range(len(prices)):
            for j in range(k, 0, -1):
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i])
                dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i])
        return dp[k][0]