Leetcode: Best Time to Buy and Sell Stock III @Python

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Recall that the problem Best Time Buy and Sell Stock solved the problem with one transaction. This problem is just the sum of the previous problem for day 1 to day i and that for day i to the end. Recording the maximum of all the sum profits for each i-th day will render the result.
For each sub-problem of the i-th day, the time complex is O(n), and the problem III is O(n^2). We can optimize by construct two arrays of the maximum one-transaction profit for day 1 to day i and that for day i to the end. Thus, we do not need to re-calculate two parts of the summation every single time. The optimized time complexity is O(n).

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        n=len(prices)
        if not prices: return 0
        mpf=[0 for i in range(n)]   #max profit for the first transaction. forward
        mpb=[0 for i in range(n)]   #max profit for the last transaction. backwrd
        low_price=prices[0]
        high_price=prices[-1]
        for i in range(1,n):
            low_price=min(low_price,prices[i])
            mpf[i]=max(mpf[i-1],prices[i]-low_price)
        for i in reversed(range(n-1)):
            high_price=max(high_price,prices[i])
            mpb[i]=max(mpb[i+1],high_price-prices[i])
        Mprofit=0
        for i in range(n-1):
            Mprofit=max(Mprofit,mpf[i]+mpb[i])
        return Mprofit