本文共 4453 字，大约阅读时间需要 14 分钟。
class Solution(object): def maxProfit(self, prices): if prices == []: return 0 minNum,ret = prices[0],0 for p in prices: minNum = min(minNum,p) ret = max(ret,p-minNum) return ret
- ：股票多次买入卖出 思路：判断第i天和第i-1天的价格差diff，把diff>0部分求和即可 计算相邻股票价格的差值，计算差值大于0的元素的和，即为最大利润
class Solution(object): def maxProfit(self, prices): if prices == []: return 0 ans = 0 for i in range(1,len(prices)): diff = prices[i]-prices[i-1] if diff>0: ans+=diff return ans
-
- ：买入卖出次数不限，但是每次需要支付一定的费用，求最大的收益,Medium 思路：
sell维护买入卖出价格(t[0],t[1])，其中t[1]为0表示未卖出 如果栈顶未卖出，且price<=buy 替换买入 如果price大于max(卖出价格，买入价格+费用）替换卖出 price作为买入价格入栈 当栈元素>1，并且合并栈顶的两组交易可以获得更大收益时，对栈顶的两个交易进行合并 a2-a1-fee+b2-b1-fee< b2-a1-fee –> a2
class Solution(object): def maxProfit(self, prices, fee): """ :type prices: List[int] :type fee: int :rtype: int """ sell = [[50000,0]] for price in prices: # 如果栈顶未卖出，且price<=buy 替换买入 if sell[-1][1]==0 and price =max(sell[-1][0]+fee,sell[-1][1]): sell[-1][1] = price # price作为买入价格入栈 elif sell[-1][1]: sell.append([price,0]) # a2-a1-fee+b2-b1-fee a2 1 and sell[-2][1] fee)
思路还是偏复杂了。。在kdd的指点，记两个状态，买p1和卖p2
p1 = max(p1,p2-price)
p2 = max(p2,p1+price-fee)
class Solution(object): def maxProfit(self, prices, fee): """ :type prices: List[int] :type fee: int :rtype: int """ size = len(prices) if size<=1: return 0 p1,p2 = -prices[0],0 for i in range(1,size): p1 = max(p1,p2-prices[i]) p2 = max(p2,p1+prices[i]-fee) return p2
-
- ：多次买入卖出，但是每次卖出后第二天不能买入，Medium
buy[i]表示时间为i前操作为买入的最大收益
sell[i]表示时间为i前操作为卖出的最大收益 rest[i]表示时间为i前操作为冷冻器的最大收益 有 buy[i] = max(buy[i-1],rest[i-1]-price) 前一天购买或者前一天冷冻当天购买 sell[i] = max(sell[i-1],buy[i-1]+price) 前一天卖出或者前一天购买当前卖出 rest[i] = max(rest[i-1],buy[i-1],sell[i-1]) buy[i]<=rest[i] 又有 rest[i] = sell[i-1] （因为rest是在sell操作之后才有的东西） 所以变成 buy[i] = max(buy[i-1],sell[i-2]-price) sell[i] = max(sell[i-1],buy[i-1]+price)
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if len(prices)<2: return 0 sell, buy, prev_sell, prev_buy = 0, -prices[0], 0, 0 for price in prices: prev_buy = buy buy = max(prev_sell - price, prev_buy) prev_sell = sell sell = max(prev_buy + price, prev_sell) return sell
计算相邻股票价格的差值 遍历i prev[i]表示从左到右第i位的最大利润 post[i]表示从右到左第i位的最大利润 ans=max(ans,prev[i]+post[i])
class Solution(object): def maxProfit(self,prices): if prices == []: return 0 size = len(prices) MIN,MAX = prices[0],prices[size-1] prev,post = [0],[0] for i in range(1,size): x = prices[i] y = prices[size-1-i] MAX,MIN = max(MAX,y),min(MIN,x) prev.append(max(prev[-1],x-MIN)) post.append(max(post[-1],MAX-y)) post.reverse() ret = 0 for i in range(size): ret = max(ret,prev[i]+post[i]) return ret
global G[i][j] 到第i天至多进行j次交易的最优利润 local G[i][j] 到第i天至多进行j次交易的最优利润，且在第i天卖出 L[i][j] = max(G[i-1][j-1],G[i-1][j-1]+diff,L[i-1][j]+diff) 说明： G[i-1][j-1]为第i-1天进行j-1次交易的最优利润，在第i天没有买入卖出行为 G[i-1][j-1]+diff为第i-1天进行j-1次交易，然后第i-1天买入，第i天卖出 L[i-1][j]+diff 为第i-1天进行第j次交易，改为第i天进行第j次交易 G[i][j] = max(G[i-1][j],L[i][j])
class Solution(object): def maxProfit(self, k, prices): """ :type k: int :type prices: List[int] :rtype: int """ if prices == [] or k ==0 : return 0 size = len(prices) if k>(size/2): return self.maxProfit1(prices) L = [[0 for i in range(k+1)] for p in prices] G = [[0 for i in range(k+1)] for p in prices] for j in range(1,k+1): for i in range(1,len(prices)): diff = prices[i]-prices[i-1] L[i][j] = max(G[i-1][j-1],G[i-1][j-1]+diff,L[i-1][j]+diff) G[i][j] = max(G[i-1][j],L[i][j]) return G[len(prices)-1][k] def maxProfit1(self, prices): if prices == []: return 0 ans = 0 for i in range(1,len(prices)): diff = prices[i]-prices[i-1] if diff>0: ans+=diff return ans
转载地址：http://qfqmi.baihongyu.com/