股票的最大利润

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

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

---

1.买卖各一次

• 从前往后构建新的序列minB,与价格序列一一对应，元素minB[i]表示在i之前（不包括i）遇到的价格最小值。
• 从后往前构建新的序列maxA,也与价格序列一一对应，元素maxA[i]表示在i之后（包括i）遇到的价格最大值。
• 计算maxA与minB对应位置元素的差（忽略首位元素），其最大值就是能获得的最大利润。

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，二者在每访问一个价格之后就可以更新。

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]，则原问题变成了一个求最大连续和子数列问题:

• 从左向右遍历,得到states=[2,0,0,2,7,11,9]
• 从右向左遍历，得到states=[2,0,0,2,7,11,0]
• states的最大元素就是最大获利11。

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)
    val = 0
    for i in range(len(pdiffs)-1,-1,-1):
        val = val + pdiffs[i] if val + pdiffs[i] > 0 else 0
        if val <= 0:
            states[i] = 0
    return max(states)

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

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

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

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

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

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

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:]都不超过一次买卖的的最大盈利。

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)