from typing import List
class Solution:
    # 错误的思路，会超时。
    def maxProfit1(self, prices: List[int]) -> int:
        if len(prices) <= 1:return 0 # 小于等于一天没法交易买和卖
        # 进行双重遍历
        for index1 in range(len(prices)):
            # 最大收益
            max_prices = 0
            for index2 in range(index1 + 1,len(prices)):
                # 第二重遍历，判断index1的最大收益
                if prices[index1] < prices[index2]:
                    if prices[index2] - prices[index1] > max_prices:
                        max_prices = prices[index2] - prices[index1]
            # 求出最大收益，
            prices[index1] = max_prices
        # 返回最大收益
        return max(prices)
    # 动态规划的解法
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:return 0 # 小于等于一天没法交易买和卖
        dp = [0 for _ in range(len(prices))]
        min_price = prices[0] #设置最低的价格，总是在价格最低的时候买入
        # 进行遍历，每一天的情况
        for index in range(1,len(prices)):
            # 判断今天的价格是否比最小值小，是的话，就改变最小值
            if min_price > prices[index]:
                min_price = prices[index]
            # 今天如果卖出的话，股票的时候是否比前一天的收益要大。
            # 今天的收益肯定是要比前几天的收益要大。，
            dp[index] = max(prices[index] - min_price,dp[index - 1])
        print(dp)
        return dp[-1]
A = Solution()
print(A.maxProfit([7,1,5,3,6,4]))
print(A.maxProfit([7,6,4,3,1]))
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄