leetcode Question 10: Best time to buy and sell stock III

Best time to buy and sell stock III

Say you have an array for which the i^th 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).

Analysis:

The idea is from dynamic programming, the max profit at day i is the max profit before day i + max profit after day i. So there is one loop O(n) to compute the max profit before each each day and another loop O(n) to get the final max profit by compute the max profit after each day reversely and combine the "before day" max profit.

Let's take an example:
prices[ ] =  1,2,4,2,5,7,2,4,9

(1) we compute the forward max profit and save it.  Forward max profit means for each day i, we want to know the max profit we can make no later than this day. Note that we only need to consider 1 transaction:
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8

(2) Now what we need is two transactions rather than one, easily we can see from the price list, if we are required exact 2 transactions, we must finish one transaction at some day i, and do the 2nd transaction after that. The max profit is the sum of max profit before day i and after day i. Day i might be every day in the price list, so there is a loop in the code.
Similar to the step(1), but in a reverse order, from the last day -1 to first, we already have the max profit before day i, mp[i], and we can compute the max profit every time for i to n-1 days (n is the number of days), similar to step(1).

e.g.
max_profit = mp[i] + mprofit

                                      i
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 6 + (9-4) = 11     (2nd trans. : buy at $4 sell at $9)

                                   i   
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 6+ (9-2) = 13    (2nd trans. : buy at $2 sell at $9)

                                i      
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 6+ (9-2) = 13  (max profit after day i not change)

......

                    i                  
prices[ ] = 1,2,4,2,5,7,2,4,9
mp[ ]     =  0,1,3,3,4,6,6,6,8
max_profit = 13  

The final max profit =13

(If you see the case that sell and buy on the same day, this is equal to the case that only 1 transaction. So the "at most 2 transactions" is satisfied)

Source Code: O(n)

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int mprof = 0;
        if (prices.size()>1){
            int maxprof = 0;
            vector<int> mp; // max profit before each element
            mp.push_back(0);
            int st = *prices.begin();
            for(int i = 1 ; i<=prices.size();i++){  //compute mp vector
                if (mprof < prices[i]-st){mprof = prices[i]-st;}
                if (prices[i]<st){st = prices[i];}
                mp.push_back(mprof);
            }
            mprof = 0;
            int ed = *(prices.end()-1);
            for (int i = prices.size()-2; i>=0; i--){
                if (mprof < ed - prices[i] + mp[i]) { mprof = ed - prices[i] + mp[i];}
                if (prices[i]>ed) {ed = prices[i];}
            }
        }
        return mprof;
    }
};

Code (Python):

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        n = len(prices)
        if (n<2):
            return 0
        st = prices[0]
        mp=[]
        mprof = 0
        for i in range(0,n):
            if (prices[i]-st>mprof):
                mprof = prices[i]-st
            if (prices[i]<st):
                st = prices[i]
            mp.append(mprof)
        
        mprof = 0
        ed = prices[-1]
        for i in range(n-2,-1,-1):
            if (ed - prices[i] + mp[i] > mprof):
                mprof = ed - prices[i] + mp[i]
            if (prices[i]>ed):
                ed = prices[i]
        return mprof