首页 > 代码库 > [leetcode]Best Time to Buy and Sell Stock III @ Python
[leetcode]Best Time to Buy and Sell Stock III @ Python
原题地址：https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
题意：
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
解题思路： 交易市场的“低买高卖" 法则(buy low and sell high‘ )
只允许做两次交易，这道题就比前两道要难多了。解法很巧妙，有点动态规划的意思：
开辟两个数组p1和p2，p1[i]表示在price[i]之前进行一次交易所获得的最大利润，
p2[i]表示在price[i]之后进行一次交易所获得的最大利润。
则p1[i]+p2[i]的最大值就是所要求的最大值，
而p1[i]和p2[i]的计算就需要动态规划了，看代码不难理解。
class Solution: # @param prices, a list of integer # @return an integer def maxProfit(self, prices): n = len(prices) if n <= 1: return 0 p1 = [0] * n p2 = [0] * n minV = prices[0] for i in range(1,n): minV = min(minV, prices[i]) # Find low and buy low p1[i] = max(p1[i - 1], prices[i] - minV) maxV = prices[-1] for i in range(n-2, -1, -1): maxV = max(maxV, prices[i]) # Find high and sell high p2[i] = max(p2[i + 1], maxV - prices[i]) res = 0 for i in range(n): res = max(res, p1[i] + p2[i]) return res
[leetcode]Best Time to Buy and Sell Stock III @ Python
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。