[数据结构与算法]python买卖股票的最好时机(动态规划)

leetcode题目：动态规划
直观做法：找极值点之差再比较

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        L = len(prices)
        if L==1:
            return 0
        min_price = prices[0]
        max_profit = 0
        i=0
        prices.append(0)
        while(i<L-1):
            i += 1
            if prices[i+1]<=prices[i] and prices[i-1]<prices[i]:
                max_profit = max(max_profit,prices[i]- min_price)
                continue
            if prices[i+1]>prices[i] and prices[i-1]>=prices[i]:
                min_price = min(min_price,prices[i])

        return max_profit

动态规划做法：大问题分解成小问题

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        L = len(prices)
        if L==1:
            return 0
        hold = -prices[0] #边界条件，第一天买入股票后利润
        nothold = 0 #边界条件，第一天不买入股票的利润

        for price in prices:
        	#比较当前利润高还是今天卖掉手持股票高(无论哪一天，手持股票是遇到的最低股票价格时买入)
            nothold = max(nothold, price + hold)
            #比较当前股票价格低还是今天价格低 
            hold = max(hold,-price)
        return nothold

转化成最大子列和问题