买卖股票的最佳时机

121&122&123_maxProfit

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

题目:

  • 121.如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
  • 122.设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
  • 123.设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:

  • 你不能在买入股票前卖出股票。
  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

示例:

输入: [7,1,5,3,6,4]

  • 121输出:5
  • 123输出:7
  • 124输出:7

第二次抽奖又抽到了组合题,还是三合一的

按顺序一道一道来吧

1. 暴力(121)

要是暴力法,只要求O(n^2)的时间复杂度的话,写起来就很简单

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
      # if all(x>y for x, y in zip(prices, prices[1:])):return 0
      max_profit = 0
      for i in range(len(prices)):
        for j in range(i+1,len(prices)):
          max_profit = max(prices[j]-prices[i],max_profit)
      return max_profit

超出时间限制


2. 在循环中把历史最小值作为买入值(121)

这样就能线性复杂度了

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
      if prices ==[]: return 0
      max_profit = 0
      hist_min_price = prices[0]
      for i in range(len(prices)):
        max_profit = max(prices[i]-hist_min_price,max_profit)
        hist_min_price =min(hist_min_price,prices[i])
      return max_profit

执行用时: 112 ms, 在Best Time to Buy and Sell Stock的Python3提交中击败了6.28% 的用户

内存消耗: 14.1 MB, 在Best Time to Buy and Sell Stock的Python3提交中击败了2.03% 的用户

ps:我已经不相信这个鬼评分系统了


3. 总是在极小值买入,下一个极大值卖出(122)

由于不限制买卖次数,很明显总是在极小值买入,下一个极大值卖出是获利最多的策略

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <2: return 0

        increase = prices[0]<prices[1]
        buy_price = prices[0]
        max_profit = 0

        for i in range(len(prices)-1):
          if prices[i] < prices[i+1] and increase: # 持续增
            continue
          elif prices[i] > prices[i+1] and not increase: # 持续减
            continue
          elif prices[i] < prices[i+1] and not increase: # 极小值
            increase = True
            buy_price = prices[i]
          elif prices[i] > prices[i+1] and increase: # 极大值
            increase = False
            max_profit += prices[i] - buy_price

        if increase:
          max_profit += prices[i+1] - buy_price
        return max_profit

执行用时: 68 ms, 在Best Time to Buy and Sell Stock II的Python3提交中击败了24.19% 的用户

内存消耗: 14 MB, 在Best Time to Buy and Sell Stock II的Python3提交中击败了0.95% 的用户


4. 贪心算法(122)

只要能赚,就完成买卖.有点傻瓜版量化交易的感觉

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <2: return 0
        max_profit = 0
        for i in range(len(prices)-1):
          if prices[i] < prices[i+1]:
            max_profit+=prices[i+1]-prices[i]
        return max_profit

执行用时: 100 ms, 在Best Time to Buy and Sell Stock II的Python3提交中击败了1.46% 的用户

内存消耗: 14.1 MB, 在Best Time to Buy and Sell Stock II的Python3提交中击败了0.95% 的用户


5. 叠加做空(123)(无法实现!)

买卖两次,可以看作单笔买卖,再叠加上一次做空操作.

首先按照第121题的思路,计算出单笔最大获利.再在一次买卖期间计算出一个最大做空获利,做空获利和单笔最大获利加起来就是两笔最大获利

但是,实际上做空获利和抛售获利是相互影响的,无法先算一个,再算另一个

6. 大神解法(123)

来自这里

理解起来颇有一点难度,我感觉自己是懂了,但表达不清楚… (建议不要看括号里的解释,容易晕:大概就是把第一次的获利表现在第二次的买价中,就能在优化第二次买卖中兼顾第一次.)

下面这张表就是在输入为[3,3,5,0,0,4,1,2]时,每次循环结束时相关变量的值,方便理解.

i_price buy_price1 buy_price2 profit1 profit2
3 3 3 0 0
3 3 3 0 0
5 3 3 2 2
0 0 -2 2 2
0 0 -2 2 2
4 0 -2 4 6
1 0 -3 4 6
2 0 -3 4 6
/*
The thinking is simple and is inspired by the best solution from Single Number II (I read through the discussion after I use DP).
Assume we only have 0 money at first;
4 Variables to maintain some interested 'ceilings' so far:
The maximum of if we've just buy 1st stock, if we've just sold 1nd stock, if we've just buy 2nd stock, if we've just sold 2nd stock.
Very simple code too and work well. I have to say the logic is simple than those in Single Number II.
*/
public class Solution {
    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = Math.max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = Math.max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = Math.max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = Math.max(hold1,    -i);          // The maximum if we've just buy  1st stock so far.
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
}
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
      if len(prices) <2: return 0
      buy_price1 = buy_price2 = prices[0]
      profit1 = profit2 = 0
      for i_price in prices:
        buy_price1 = min(buy_price1 ,i_price            )
        profit1    = max(profit1    ,i_price-buy_price1 )
        buy_price2 = min(buy_price2 ,i_price - profit1  )
        profit2    = max(profit2    ,i_price-buy_price2 )
      return profit2

执行用时 : 80 ms, 在Best Time to Buy and Sell Stock III的Python3提交中击败了69.85% 的用户

内存消耗 : 14 MB, 在Best Time to Buy and Sell Stock III的Python3提交中击败了0.00% 的用户

7. 其他解法(123)

我认为以下的算法没6. 大神解法那么优秀,所以只列出思路,不写代码

  • 切两半法: 分别找到[:i]和[i:]两部分的最大收益,然后引出动态规划,或双向扫描等常见解法
  • 递推法: 计算局部最优,再比较从而得出全局最优
本文总字数: 3890