股票的最大利润

Posted on | In |

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可获得的最大利润是多少？

例子： 例如，一只股票在某些时间节点的价格为[9,11,8,5,7,12,16,14]。如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.

1.买卖各一次

  • 从前往后构建新的序列minB,与价格序列一一对应，元素minB[i]表示在i之前（不包括i）遇到的价格最小值。
  • 从后往前构建新的序列maxA,也与价格序列一一对应，元素maxA[i]表示在i之后（包括i）遇到的价格最大值。
  • 计算maxA与minB对应位置元素的差（忽略首位元素），其最大值就是能获得的最大利润。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def maxProfit(prices):
    lp = len(prices)
    
    minB = []
    for i in range(1,lp): # 由前向后生成minB序列
        if len(minB)==0:
            minB.append(prices[i-1]) 
        else:
            minB.append(min(prices[i-1],minB[i-2]))

    maxA = []
    for i in range(lp-1,0,-1): # 由后向前生成maxA序列
        if len(maxA) == 0:
            maxA.insert(0,prices[i])
        else:
            maxA.insert(0,max(maxA[0],prices[i]))
    return max([maxA[i]-minB[i] for i in range(lp-1)])

在访问第i个价格之前，记录所遇到的最低价格minP和最大盈利maxProfit，二者在每访问一个价格之后就可以更新。

1
2
3
4
5
6
7
8
9
10
def maxProfit(self, prices):
    lp = len(prices)
    if lp < 1:
        return 0
    
    minP, maxProfit = prices[0], 0 
    for i in range(lp):
        maxProfit = max(maxProfit, prices[i]-minP)
        minP = min(minP,prices[i])
    return maxProfit

第i天买第j天卖，收益函数prices[j]-prices[i] = prices[j]-prices[j-1]+prices[j-1]-prices[j-2]+...+prices[i]-prices[i]等价于从i到j相邻两天价格差的求和。收益函数最大，也就是求相邻价格差组成的序列的最大和子序列。

将原输入数组[9,11,8,5,7,12,16,14]进行改造，得到相邻两天的价格差的数组[2,-3,-3,2,5,4,-2]，则原问题变成了一个求最大连续和子数列问题: 以\(f(i)\)表示以从左到右第\(i\)个数字结尾的子数组的最大和，则\(max[f(i)]\)就是全局的最大和。用动态规划，有如下递推公式： \[f(x)= \begin{cases} pdiffs[i],\qquad i=0 \vee f(i-1)\le 0 \\ f(i-1)+pdiffs[i],\quad i\ne 0 \wedge f(i-1)\ge 0 \end{cases} \]

1
2
3
4
5
6
7
8
9
10
def maxProfit(prices):
    if len(prices) <= 1:
        return 0
    pdiffs = [prices[i]-prices[i-1] for i in range(1,len(prices))]
    states = []
    val = 0
    for i in range(len(pdiffs)):
        val = val + pdiffs[i] if val + pdiffs[i] > 0 else 0
        states.append(val)
    return max(states)

上面求最大连续和子数列的复杂度是2n，再加上求价格差和最大值，总复杂度是4n，即O(N)。

2.多次买卖，两次买卖之间无交叉

很简单，相邻两天的价格差的数组，将其大于0的元素求和即得到多次买卖的最大利润。

如果一次买卖决策是第i天买入第j天卖出，有如下两种情形：

  • 如果j>i+1，多个连续价格差的和。易知利润等价于i到j天的价格差之和。而且同时i、j之间的相邻两天价格差必然全为非负。
  • 如果j=i+1，单独一个价格差，其左右相邻两个价格差必为负。

两种情况都是为正数的价格差的求和。 

1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        sumProfit = 0
        for i in range(1,len(prices)):
            diff = prices[i]-prices[i-1]
            if diff > 0:
                sumProfit += diff 
        return sumProfit

3.至多两次买卖，两次买卖之间无交叉

令i=0..n-1，定义

  • dp1[i]是子序列prices[0-i]这个i+1序列的最多一次买卖的最大盈利，
  • dp2[i]是子序列prices[i:]这个n-i序列的最多一次买卖的最大盈利。
  • 则dp[i]=dp1[i]+dp2[i]表示第i天前后两个子序列prices[0-i]和prices[i:]都不超过一次买卖的的最大盈利。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxProfit(self, prices):
        n = len(prices)
        if n < 2:
            return 0
        dp1 = [0 for _ in range(n)]
        dp2 = [0 for _ in range(n)]
        minval = prices[0]
        maxval = prices[-1]
        #前向   
        for i in range(1,n):
            dp1[i] = max(dp1[i-1], prices[i] - minval)
            minval = min(minval, prices[i])
        #后向    
        for i in range(n-2,-1,-1):
            dp2[i] = max(dp2[i+1], maxval - prices[i])
            maxval = max(maxval, prices[i])
        
        dp = [dp1[i] + dp2[i] for i in range(n)]
        return max(dp)