力扣-0121.买卖股票的最佳时间【Python】

LeetCode0121.买卖股票的最佳时间【简单】【Python】【贪心】【动态编程】问题LeetCode假设你有一个数组，其中第i个元素是给定股票在第i天的价格。如果您最多只被允许完成一笔交易（即，买入和卖出一股股票），请设计一个算法来找到最大利润。请注意，您不能在买入股票之前卖出股票。示例1：输入：[7,1,5,3,6,4]输出：5解释：第2天买入（价格=1），第5天卖出（价格=6),利润=6-1=5。不是7-1=6，因为卖出价需要大于买入价。示例2：输入：[7,6,4,3,1]输出：0解释：在这种情况下，没有交易完成，即最大利润=0。给定一个数组，其第i个元素是给定股票在第i天的价格。如果您最多只能完成一笔交易（即买卖一只股票），请设计一种算法来计算您可以获得的最大利润。请注意，您不能在买入前卖出股票。示例1：输入：[7,1,5,3,6,4]输出：5解释：第2天买入（股价=1），第5天买入（股价=6）卖出，最大利润=6-1=5。注意利润不能是7-1=6，因为卖出价需要大于买入价。示例2：输入：[7,6,4,3,1]输出：0解释：本例中没有交易完成，所以最大利润为0解题思路——贪婪买入和卖出同时计算.当buy>price时，更新buypricebuy。当利润<价格-买入时，更新利润profit。时间复杂度：O(len(prices))空间复杂度：O(1)Python3codeclassSolution:defmaxProfit(self,prices:List[int])->int:#solutionone:greedyprofit,buy=0,0x7FFFFFFFforpriceinprices:ifbuy>price:buy=price#尝试以小价买入股票ifprofitint:#解决方案二：动态规划#K=1dp_i_0=0dp_i_1=float('-inf')#Negativeinfinityforiinrange(len(prices)):#昨天没有股票，昨天有股票，今天卖出了dp_i_0=max(dp_i_0,dp_i_1+prices[i])#dp_i_0和dp_i_1可以看作变量,stored是上次的值，也就是昨天#昨天有库存，昨天没有库存。今日购买dp_i_1=max(dp_i_1,-prices[i])返回dp_i_0代码地址GitHub链接参考一种排除6个库存问题的方法