买卖股票的最佳时机题目来源：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stockTopicGiven一个数组，它的第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。解题思路将差分问题转化为区间求和问题。这里用牛顿-莱布尼茨公式来说明下转换的问题：但是这里的F()不是连续的，而是离散的，a和b代表数组的下标。这里F()表示的数组称为前缀和。前缀和：数组的某个下标（包括该元素）之前的所有数组元素的总和。这样，差分问题就可以转化为区间和问题。最大连续子数组和的问题可以使用动态规划来解决。dp[i]表示以i结尾的最大连续子数组和。结合题意，状态转移方程为：dp[i]=max(0,dp[i-1]+diff[i])其中dp[i]数组可以优化，所以上面的公式可以改为：last=max(0,last+diff[i])其中diff[i]=prices[i+1]-prices[i]，表示相隔两天的价格差的股票。所以上面的公式可以进一步优化为：last=max(0,last+prices[i+1]-prices[i])代码实现类解：defmaxProfit(self,prices:List[int])->int:last,profit=0,0foriinrange(len(prices)-1):last=max(0,last+prices[i+1]-prices[i])profit=max(profit,last)回报盈利实现结果参考https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/以上就是利用数学方法将差值转化为区间之和来求解《买卖股票的最佳时机》问题的主要内容。欢迎关注微信公众号《书所集录》欢迎关注微信公众号《书所集录》
