股票的最大利润

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

例子：
例如，一只股票在某些时间节点的价格为[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(prices):
    lp = len(prices)
    minP, maxProfit = None, 0 
    for i in range(lp):
        maxProfit = max(maxProfit, 0 if minP is None else prices[i]-minP)
        minP = prices[i] if not minP else min(minP,prices[i])
    return maxProfit

---

将原输入数组[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):
    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天卖出，则利润等价于i到j天的价格差之和。

def maxProfit(prices):
    pdiffs = [prices[i]-prices[i-1] if prices[i]-prices[i-1]>0 else 0  for i in range(1,len(prices))]
    return sum(pdiffs)

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

仍然基于相邻两天的价格差的数组[2,-3,-3,2,5,4,-2]，找到局部最大的子数列，求子数列之和最大的两个的和。

• 从左向右遍历,得到states=[2,0,0,2,7,11,9]
• 从右向左遍历，得到states=[2,0,0,2,7,11,0]
• 去掉局部最大子数列的中间值得到states=[2,0,0,0,0,11,0]，最大的两个元素是2和11。
• 可知买卖两次收益最大，分别获利2和11，一共获利13。

def maxProfit(prices):
    pdiffs = [prices[i]-prices[i-1] for i in range(1,len(prices))]
    
    # 下面两个过程，一个从左往右遍历，一个从右往左遍历，最终生成的states不但可以根据元素是否为0来区*部最大子数列的界限，
    # 而且states的局部最大子数列对应的最右元素是该子数列的局部最大值。
    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
    
    for i in range(len(states)-1): # 去掉局部最大子数列的states的中间过程值
        if states[i+1] > 0:
            states[i+1] = 0
    max1, max2 = 0, 0 # max1次大，max2最大
    for i in range(len(states)-1):
        if states[i] > 0:
            if states[i] > max2:
                max2, max1 = states[i], max2
            elif states[i] > max1:
                max1 = states[i]
    
    
    return max1+max2