买卖股票问题

问题地址：

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

解决方法：

#best-time-to-buy-and-sell-stock-i
from typing import *
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        length = len(prices)
        if not prices or length <= 1:
            return maxProfit
        
        minValue = float("inf")
        maxValue = float("-inf")
        result = 0
        for i in range(length-1):
            
            if prices[i] < minValue:
                minValue = prices[i]
            
            if prices[i+1] > prices[i]:
                maxValue = prices[i+1]
                result = max(result, maxValue - minValue)
            
        return result

#best-time-to-buy-and-sell-stock-ii
from typing import *
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i, value in enumerate(prices):
            if i != 0 :
                if value > prices[i-1]:
                    result += value - prices[i-1]
            
        return result

#best-time-to-buy-and-sell-stock-iii
from typing import *
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        k = 2
        
        buys = [float("inf") for _ in range(k)]
        sells = [0 for _ in range(k)]
        
        for v in prices:
            for i in range(k):
                if i == 0:
                    buys[i] = min(buys[i], v)
                    sells[i] = max(sells[i], v - buys[i])
                else:
                    buys[i] = min(buys[i], v - sells[i-1])
                    sells[i] = max(sells[i], v - buys[i])
        return sells[-1]

#best-time-to-buy-and-sell-stock-iv
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        
        if k == 0 or not prices or len(prices) <= 1:
            return 0
        
        if k >= len(prices)//2:
            result = 0
            for i, v in enumerate(prices):
                if i != 0 and v - prices[i-1] > 0:
                    result += v - prices[i-1]
            return result
        
        buys = [float("inf") for _ in range(k)]
        sells = [0 for _ in range(k)]
        
        for v in prices:
            for i in range(k):
                if i == 0:
                    buys[i] = min(buys[i], v)
                    sells[i] = max(sells[i], v - buys[i])
                else:
                    buys[i] = min(buys[i], v - sells[i-1])
                    sells[i] = max(sells[i], v - buys[i])
        return sells[-1]